0
$\begingroup$

Why does Dijkstra's algorithm not re-evaluate/re-expand nodes who have been expanded and later had their weight changed?

For example, in the accepted answer of this question (link), if the algorithm simply understands that d(b) has been updated and it should re-expand b, the shortest cost would be found.

Am i missing something?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Since Dijkstra's algorithm always expands the shortest path first, the first time we reach a node will be along the shortest path to that node. That is the key insight that allows the algorithm to be efficient compared to a breadth-first-search.

There is no way to construct a graph where no costs are negative and there exists a path from a to b shorter than the one Dijkstra's algorithm finds.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So you're saying that if it were to re-expand an already expanded node after its value has changed it would make the algorithm less efficient than other algorithms, eliminating its purpose? $\endgroup$
    – Ulad Kasach
    Commented Apr 20, 2016 at 22:58
  • $\begingroup$ It would be less efficient, yes. Also, looking at new paths to an already reached would be completely useless, since we've already found the shortest path to that node. $\endgroup$
    – Drathier
    Commented Apr 20, 2016 at 23:30
  • $\begingroup$ If a node with a larger distance from the starting node has a negative path then we have not necessarily already found the shortest path. $\endgroup$
    – Ulad Kasach
    Commented Apr 20, 2016 at 23:31
  • $\begingroup$ Dijkstra's algorithm assumes there are no negative cycles, as I mentioned in the answer above. If you need to handle negative cycles, use Bellman–Ford algorithm instead. $\endgroup$
    – Drathier
    Commented Apr 20, 2016 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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