# Should I implement TSP or Dijkstra?

I was asked to create a shortest path algorithm in java to use with OSRM.

I want to create a route between some points (normally more than 3). The first one, will be the starting point and also the last point (close route). Other point have to be the last before the last one and rest of points have to be ordered taking the shortest path between the first and the last before the first again.

I think this is no possible to do with TSP because TSP doesn't have a known first point and also it is not possible to determine if a point have to be visited in a concrete position. Is it possible?

So I think I should use dijkstra for that and create a route between the starting point and the last before the starting point, after that, add the starting point to the route.

Talking about Dijkstra with some friends, I was adviced about Dijkstra doesn't visit all points always, maybe some of them are left out the route.. .Is this true? Also I hear about Dijkstra doesn't create a route, it creates a tree... also, is it true?

Which algotirhm should I implement?

Thanks and sorry for brick ;)

• How does your question differ from gis.stackexchange.com/questions/30305/…? – whuber Aug 29 '12 at 16:56
• Differs in having a pre last point fixed in route. Not so much but I want to know if it can be possible in TSP or not. – Biribu Aug 30 '12 at 10:32
• Could you please explain more clearly what you mean by a "pre last point fixed in route"? – whuber Aug 30 '12 at 11:09
• English is not my mother languaje, sorry. I mean, I have some nodes. I want to start in one of them and finish in the same again. But, I want that before arriving to the origin again, pass through other node, leaving this other node always for the N-1 possition. If I have 5 nodes: N1,N2,N3,N4,N5 (N5 will be the pre last node) I want a route between N1 and N5 but N5 always closest to Start point. Something like: before going back home, have to pass through one place, but this place just can be reached after passing through rest of nodes.... Maybe I am confusing you more... – Biribu Aug 30 '12 at 13:48
• The problem seems clear--and it's equally clear this is TSP, because the solution is to solve the TSP from node N1 to N5, passing through N2, N3, and N4. You might as well adopt a brute-force solution for a problem this small: just compute all six permutations of the possible intermediate points and choose the best. – whuber Aug 30 '12 at 13:52