# Can the Dijkstra algorithm work with a negative arc?

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$$.