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 😉
Best Answer
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.