2

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 ;)

|improve this question
  • 3
    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
1

If I understand you want to implement a nearest-neighbor algorithm in java(?) Nearest-neighbor is a well known not very efficient tsp (or vrp) solving approach... And you have to (is it really a constraint?) use OSRM to calculate the distance between all your points. OSRM is a c++ program which uses boost and is osm compliant. Maybe you should consider using something else, like pgrouting for example, using the same (openstreetmap) data and contains various shortest-path options; it would save you the java native interface implementation (and be more easily cross-platform able).

Dijkstra creates a tree starting from a given point. This tree can be used to calculate the distances between your starting point and all the other vertices you want (if a route exists in your graph) by adding the weigth of each edge. It seems a fair way to generate a distance matrix.

I think you should have a look at some VRP algorithms... Good luck.

|improve this answer
  • I have to use OSRM, I can't use pgrouting. I already have all distances between nodes calculated, I kkep that info in a txt file. I will check VRP algorithm, thanks! – Biribu Aug 30 '12 at 7:57
0

Dijkstra is a shortest path algorithm and its return a spanning tree from one node to all others nodes in the graph. Then, if your graph has N nodes and n_0 is the origin node, Dijkstra will return N shortest paths, each of them starting from n_0 to n_i with i in N. For this reason, Dijkstra isn't a inmediate alternative to TSP algorithm because is not finding the minimun path that conect all nodes in the graph.

|improve this answer
  • I already have dijkstra algorithm implemented. I did some days ago and I followd this link: en.wikipedia.org/wiki/Dijkstra's_algorithm But, I think it is not possible to create a spanning tree with this, I always pick up a node and add it to the route ordered, so I would just have: N0, N3, N2, N4... ordered... I will check info about TSP, but I don't know how to implement about have a Nn-1 point always in the same place – Biribu Aug 30 '12 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.