The shortest path between 2 given nodes of a cyclic directed weighted graph

Question

How to get the shortest path between 2 given nodes of a cyclic directed weighted graph as a list of nodes?

Answer 1

I think dijkstra's algorithm is what you are looking for:

• http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

To get the shortest path as a list of nodes you have to use an additional map (of the type node -> node) to keep track of your node's predecessors.

Assume we find the shortest path from A to C over B.

Start with an empty map. When updating the tentative distance from node A to node B, you also insert the relation B -> A into your map (Wich means A is predecessor of B). If you find an even shorter distance to B, you overwrite the map entry.

When your algorithm has finished your map contains the entries B -> A and C -> B. Now you can trace your way back through the map and create a list.