Find the shortest path with the least number of edges

Question

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 1

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).