I know Dijkstra's algorithm finds the shortest path from one source to all destinations. But let say we found 2 paths to a vertex from the source which are minimum distance. So the issue is the path should be chosen based on number of fewest edges. How to do that ? what can be modified in algo ?
Two distances can be computed for each node: $d_1$, the least total cost of edges along a path to the node as in the standard algorithm, and $d_2$, the least number of edges in a path to the node that costs $d_1$. Visited nodes can update the distances of their neighbors by first comparing $d_1$ and breaking ties using $d_2$.
- Add some really small number $\varepsilon$ to the weight of each edge (how small – it depends on the graph).
- Instead of using some small numbers, you can also use pairs $w'_e = (w_e, 1)$ with pointwise addition and ordered lexicographically.
I hope this helps $\ddot\smile$