CODEWITHSUNDEEP
graph
Nice Books
Nice Books

Reputation: 1861

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

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

Upvotes: 1

Views: 3819

Answers (1)

Patrick Schmidt
Patrick Schmidt

Reputation: 453

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

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.

Upvotes: 3

Related Questions