Using Dijkstra's algorithm with negative edges?
Posted
by
Riddler
on Stack Overflow
See other posts from Stack Overflow
or by Riddler
Published on 2012-06-24T03:13:44Z
Indexed on
2012/06/24
3:15 UTC
Read the original article
Hit count: 341
Most books explain the reason the algorithm doesn't work with negative edges as nodes are deleted from the priority queue after the node is arrived at since the algorithm assumes the shortest distance has been found. However since negative edges can reduce the distance, a future shorter distance might be found; but since the node is deleted it cannot be updated.
Wouldn't an obvious solution to this be to not delete the node? Why not keep the node in the queue, so if a future shorter distance is found, it can be updated? If I am misunderstanding the problem, what is preventing the algorithm from being used with negative edges?
© Stack Overflow or respective owner