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: 342

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

Related posts about algorithm

Related posts about computer-science