16

What if the only negative edge costs are coming from the initial node? Will the algorithm still work?

I feel like yes, because I can't think of a counter-example, but I'm having trouble proving it. Is there a counter-example?

Negative edges are a problem for Dijkstra's because there's no guarantee that the edge you pick produces the shortest path if there is an edge you can pick later that is largely negatively weighted. But if the only negative edges are coming out of the initial node, I don't see the problem.

I'm not looking for an algorithm. I'm looking for some insight into the Dijkstra's.

I'm talking about a directed graph, if that makes a difference.

2
  • Are you trying to find an algorithm that works, or learn something about Dijkstra's algorithm?
    – Beta
    Sep 30, 2010 at 18:16
  • I'm not looking for an algorithm. I put the tag there because the question is about an algorithm. Sep 30, 2010 at 18:18

3 Answers 3

21

The trouble with having a negative-cost edge is that you can go back and forth along it as many times as you like.

If you impose a rule that an edge may not be used more than once, you still have a problem. Dijkstra's algorithm involves marking a node as "visited", when it's distance from the initial node is considered know once and for all. This happens before all of the edges have been examined; the shortest path from the initial node to node X has been found, all other paths from the initial node are already longer than that, nothing that is discovered later can make those paths shorter. But if there are negative-cost edges somewhere, then a later discovery can make a path shorter, so it may be that a shorter path exists which Dijkstra will not discover.

If only the edges that connect to the initial node may have negative costs, then you still have problem, because the shortest path might involve revisiting the initial node to take advantage of the negative costs, something Dijkstra cannot do.

If you impose another rule that a node may not be visited more than once, then Dijkstra's algorithm works. Notice that in Dijkstra's algorithm, the initial node is given an initial distance of zero. If you give it some other initial distance, the algorithm will still find the shortest path-- but all of the distances will be off by that same amount. (If you want the real distance at the end, you must subtract the value you put in.)

  1. So take your graph, call it A, find the smallest cost of any edge connected to the initial node, call it k which will be negative in this case).
  2. Make a new graph B which you get by subtracting k from the cost of each edge connected to the initial node. Note that all of these costs are now non-negative. So Dijkstra works on B. Also note that the shortest path in B is also the shortest path in A.
  3. Assign the initial node of B the distance k, then run Dijkstra (this will give the same path as running with an initial distance of zero). Compare this to running Dijkstra naively on A: once you leave the initial node everything's the same in the two graphs. The distances are the same, the decisions are the same, the two will produce the same path. And in the case of A the distace will be correct, since it started at zero.
12

Counter-example:

Graph G = (V, E), with vertices V = {A, B}, edges E = {(A, B), (B, A)} and weight function w(A, B) = -2, w(B, A) = +1.

There's a negative weight cycle, hence minimum distances are undefined (even using A as initial node).

2
  • 1
    Dijkstra's algorithm will tell you that a minimum weight path from A to B is [A, B], with weight -2. But there are paths from A to B with less weight than that, for example [A, B, A, B] with weight -3. Sep 30, 2010 at 20:49
  • Marked as the answer because I asked for a counter-example or a proof otherwise. Sep 30, 2010 at 21:49
0

Dijkstra's algorithm doesn't produce correct answer for graph with negative edge weights (even if graph doesn't have any negative weight cycle). For e.g. it computes incorrect shortest path value between (A, C) for following graph with source vertex A,

A -> B : 6
A -> C : 5
B -> D : 2
B -> E : 1
D -> E : -5
E -> C : -2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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