Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 ?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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:

  • $V = \{a,b,c,d,e,f,g\}$ and,
  • $E = \{(a,b),(b,d),(d,e),(e,f),(f,g),(g,c),(c,a)\}$.

enter image description here

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 !

share|improve this answer
    
thank you very much, this example was exactly what i needed. –  Hasan Tahsin Dec 31 '12 at 17:25
    
You are welcome, and thanks for the draw ! :) –  AJed Dec 31 '12 at 17:44

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.

share|improve this answer
    
thank you for your answer, but your answer is only valid for directed graphs. I asked for an example about an undirected graph. Dijikstra works in your example if the graph is undirected ie.: (a,b),(b,a),(b,c),(c,b),(c,a),(a,c) –  Hasan Tahsin Dec 30 '12 at 16:53
    
@moller1111, the dijikstra algorithm is single-source algorithm: it starts from A, then adds B,C, outputting the shortest path from A to B,C to be 1, -99. –  Strin Dec 31 '12 at 3:30
    
i have to emphazize the magic word in this question again: "UNDIRECTED". i need an example of an UNDIRECTED graph where the algorithm fails. In your case the algorithm finds the cost of shortest edges from the start vertex to other vertices correctly if the graph is UNDIRECTED. Your description is true for a directed graph, but not for an undirected one. –  Hasan Tahsin Dec 31 '12 at 4:16
    
@moller1111, sorry for the inconvenience. I have fixed the answer, –  Strin Dec 31 '12 at 9:33
    
This is a perfectly valid simple UNDIRECTED example to me. In undirected graphs $(a,c)$ is the same as $(c,a)$ of course. –  Hendrik Jan Dec 31 '12 at 18:55

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:

enter image description here

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.