I am debugging a legacy code where a road network has been represented by Boost Graph.
The A_Star search doesn't give me the shortest path between 2 certain points and I know boost can't be wrong (not until I have debugged my code a thousand times).
To debug manually, I need to know how I can print all possible paths between 2 vertices. In my output, each path should be represented by a series of edges and their corresponding weights.
I value your kind help and comments
A* is based on an heuristic. If the legacy uses A* it means the problem is more complex then just find the shortest path.
To find the shortest path between 2 vertices, there are certain Graph Algorithms, Dijkstra is the easyest one to implement (make sure to make it with loop checking as well). These are deterministic.
If you need to know ALL paths between 2 vertices, this one is NP complete , meaning you need to go with backtracking.
A* is generally used to solve NP complete problems. The results isn't THE BEST path, is just ONE VERY GOOD PATH FOUND IN DECENT TIME .
The heuristic from A* is used to drop recursions or transform the algorithm from a backtracking to a Breadth-first-search (usually the latter).
An example of difference between an problem solvable by A* algorithm and a Dijkstra would be as following (from the top of my head ) :
Find the shortest roads in Manhatan from Corner X,Y to corner X1,Y1 (solvable by Dijkstra or in case of Manhatan BFS)
Pick the best route in Manhatan from Corner X,Y to corner X1,Y1 considering traffic and traffic lights , according to certain hours (so it's a significant difference between the cost for edge 1,1 to 1,2 if you arrive at 1,1 at t0 and if you arrive at 1,1 at t1 > t0, example : that portion of the road gets blocked at t1 for 10 hours ).