Failing Dijkstra's algorithm with a graph contains a negative edge

Question

I'm looking for an example of a graph with exactly one negative edge such that Dijkstra's algorithm will fail to produce the correct shortest path.

I've seen the following example but I think it's wrong. The last vertex to pop out from the priority-queue will be $A$, and so we will relax the edge $A\to E$ and the correct path will be chosen - $S\to A\to E$

Answer 1

If you consider your example graph and add a vertex F connected to E by an edge of length 1. Then A is still the last vertex to pop out of the priority queue and the label of E will be updated. However, the label of F will not be updated again and stay 3 (via route (S)-(B)-(E)-(F)) although 2 would be optimal (via route (S)-(A)-(E)-(F)).

Answer 2

I have seen at least two different versions of Dijkstra's algorithm. During extract and relaxation step, we can have:

Version 1: Extract a vertex $x$ from the priority queue $Q$ and relax $(x,y)$ for each vertex $y$ which is adjacent to $x$ and such that $y \in Q$.

Version 2: Extract a vertex $x$ from the priority queue $Q$ and relax $(x,y)$ for each vertex $y$ which is adjacent to $x$.

Both versions assume all edge-weights are non-negative. Your example does show that if an edge-weight is negative, then Dijkstra Version 1 can fail. Your example does not show Dijkstra Version 2 can fail, and so you do need to find another example. It seems slightly more difficult to come up with an example to show that Dijkstra Version 2 can also fail if an edge-weight is negative. To construct such an example, just add to your graph another vertex $F$ and an edge $(E,F)$ with weight $1$. Observe that the vertices are extracted from the priority queue in order $S, B, E, F, A$. When $F$ is extracted, the distance to $F$ is $3$. In the next step, when $A$ is extracted and $(A,E)$ relaxed, only the distance to $E$ is updated, ie the distance to $F$ does not get updated from 3 to 2. So Dijkstra Version 2 fails to give the shortest path to $F$. Notice that to construct such an example, we created a negative-weight edge which contributes to the shortest distance to a vertex which is not the end-vertex (immediate neighbor) of this negative-weight edge.