0
$\begingroup$

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 ?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

Hint:

  • 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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.