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?


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.

  • $\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 Apr 20 '16 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$ – Filip Haglund Apr 20 '16 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 Apr 20 '16 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$ – Filip Haglund Apr 20 '16 at 23:35

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.