When there is no negative circle in the graph? And can Dijkstra not work even if there is a negative arc that does not create a negative cycle?


The most common implementation of Dijkstra's algorithm (for example, the one you find on Wikipedia), will not work correctly in this case, because once a node is extracted from the priority queue, its label (distance from the source) will never be revised. Consider the following example: there are four nodes $a,b,c,d$ (node $a$ is the source), and four arcs: $a \rightarrow b$ with cost 10, $a \rightarrow c$ with cost 4, $b \rightarrow c$ with cost -8, and $c\rightarrow d$ with cost 1. With the classic implementation, Dijkstra's algorithm will extract node $c$ from the queue before node $b$, and hence will report 5 as the length of the shortest path from $a$ to $d$, while the correct answer is 3.

There is, however, a conceptually simple modification that guarantees correctness of the algorithm on any instance with negative weights but no negative cycles. You simply put back a node in the priority queue after you discovered a shorter path to it. In the above example, after the node $b$ is expanded we discover a shorter path to $c$, and put $c$ back in the queue. Expanding $c$ one more time allows to find the correct path to $d$.

Note however that, while correct, the running time of this "revised Dijsktra" is no longer the same as the original implementation, because now we may have to expand the same node multiple times. In fact, the running time can be exponential in the number of nodes.

| cite | improve this answer | |

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.