Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
INPUT: "an undirected, weighted graph (negative weights allowed)"
Could someone give an example for an undirected graph with negative edges where Dijkstra's algorithm doesn't work?
As far as i understood it only fails by directed graphs in case of negative edges.
Am i right ?
It has been a long time, honestly. But I am following the pseudocode given in wikipedia.
It is basically the same standard proof that depends on directed graph argument and a triangle graph, but simply consider longer paths. (Actually, after reading this solution below, you will realize that even a triangle graph will generate wrong results if it contains a negative edge).
Consider an undirected ring graph $G = (V,E)$ where:
Let's every edge have weight 1 except $(e,f)$ has weight -100. This means that you to get from $a$ to $b$ you should take the other side of the ring. We want to find the distance from $a$ to every other node. This is denoted $dist(v)$ for each $v \in V$.
At the last two iterations of the algorithm, we have $e$ and $f$ left in the queue, and $dist(e)$ and $dist(f)$ both equals to 3. Let's pick the minimum of them (i.e. $e$) and remove it from the queue. Here you will update $dist(f)$ to 3 - 100 = -97. Then you will do the same with $f$ (the queue of vertices is empty now). You will update $dist(g)$ to 2 - 100 = -98 and $dist(e)$ to -97 - 100 = -197. The algorithm terminates since the queue of vertices is empty. And it is just mess !
It's not just Dijkstra's algorithm that doesn't work. Other standard shortest-path algorithms like Bellman-Ford don't work on undirected graphs with negative edges either.
The problem is that these algorithms compute a shortest path tree rooted at the source vertex $s$. Specifically, both algorithms assign a predecessor (or parent) to each vertex $v$, which is the second-to-last vertex on the shortest path from $s$ to $v$. This works for undirected graphs with positive edges and arbitrary directed graphs, because in those graphs, any prefix of a shortest path is another shortest path.
But shortest paths in undirected graphs with negative edges don't necessarily define trees. Consider the following simple example:
The shortest path from $s$ to $x$ passes through $y$ and has length zero. Symmetrically, the shortest path from $s$ to $y$ passes through $x$ and has length zero. Both of these shortest paths use the edge $xy$, but in opposite directions. The edges $sx$ and $sy$ are prefixes of shortest paths, but they are not themselves shortest paths.
Shortest paths can still be computed in polynomial time in these graphs (provided they have no negative cycles), but the algorithms are much more complicated.
Think about a "triangle"(3-clique): an undirected graph $G(V,E)$ with three vertices $a,b,c$ and edges $(a,b),(b,c),(c,a)$. Assign cost $w_{a,b} = 1$, $w_{b,c} = -100$, $w_{c,a} = 100$. If we want to find the shortest path from $a$ to $b$, Dijikstra greedily chooses $b$ via edge $(a,b)$, which has cost one. However, the shortest path from $a$ to $b$ is $(a,c),(c,b)$, which has cost only 0.
In fact, the proof of the correctness of Dijikstra algorithm relies on the fact that all edges have non-negative weights such that the greedy algorithm always stays ahead.
