Find the shortest path with the least number of edges

algorithm dijkstra shortest-path
Jacek Trociński picture Jacek Trociński · Nov 18, 2013 · Viewed 9.6k times · Source

I need to modify Dijkstra's algorithm so that if there are several shortest paths I need to find the one with minimum number of edges on the path.

I've been stuck on how to use Dijkstra's method to find multiple shortest paths, how do you do that? doesn't it always output only 1 shortest path? pseudo code or any general direction would be very helpful.

Answer

FUD picture FUD · Nov 18, 2013

Instead of assigning every node with the distance from source you can assign the number of edges traversed so far also. So each node will have (distance,edges) instead of distance only. Everything else works as usual and for every terminal node you record the one with minimum value of (distance,edges).

Related questions

Why doesn't Dijkstra's algorithm work for negative weight edges?

Can somebody tell me why Dijkstra's algorithm for single source shortest path assumes that the edges must be non-negative. I am talking about only edges not the negative weight cycles.

Read More
Negative weights using Dijkstra's Algorithm

I am trying to understand why Dijkstra's algorithm will not work with negative weights. Reading an example on Shortest Paths, I am trying to figure out the following scenario: 2 A-------B \ / 3 \ / -2 \ / C From the website: Assuming the edges are all …

Read More
Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?

After a lot of Googling, I've found that most sources say that the Dijkstra algorithm is "more efficient" than the Bellman-Ford algorithm. But under what circumstances is the Bellman-Ford algorithm better than the Dijkstra algorithm? I know "better" is a …

Read More