6
$\begingroup$

Most books explain the reason the algorithm doesn't work with negative edges as nodes are deleted from the priority queue after the node is arrived at since the algorithm assumes the shortest distance has been found. However since negative edges can reduce the distance, a future shorter distance might be found; but since the node is deleted it cannot be updated.

Wouldn't an obvious solution to this be to not delete the node? Why not keep the node in the queue, so if a future shorter distance is found, it can be updated? If I am misunderstanding the problem, what is preventing the algorithm from being used with negative edges?

$\endgroup$

migrated from stackoverflow.com Jun 25 '12 at 11:54

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ stackoverflow.com/questions/6799172/… $\endgroup$ – mda Jun 24 '12 at 3:23
  • $\begingroup$ @Riddler: There is a fundamental problem if you don't delete the node: Since the distance to the source node is always 0. how would you proceed to the next node (just for a positive weight graph)? $\endgroup$ – nhahtdh Jun 24 '12 at 4:05
  • $\begingroup$ @nhahtdh I don't understand your question. Could you rephrase it? $\endgroup$ – user1422 Jun 24 '12 at 4:45
  • $\begingroup$ @Riddler: Distance to source node is 0, and source node is always the first node in the queue when you enter the loop of Dijkstra algorithm (regardless of implementation). However, on the 2nd iteration of the loop, how will you choose the next node to process? Since distance to source node is 0 and is the smallest in a positive weight graph, it will be processed again. $\endgroup$ – nhahtdh Jun 24 '12 at 4:57
  • $\begingroup$ @nhahtdh What if you did the following: $\endgroup$ – user1422 Jun 24 '12 at 18:22
6
$\begingroup$

Short answer is that Dijkstra is a greedy algorithm, meaning we assume that we have made the best choice possible in every step of the algorithm. With negative edges, this is no longer possible and thus a greedy algorithm will not suffice.

Here's an analogy: (that might help, or confuse even more) Take a convex optimization problem and poke a concavity into it. Now ask the question why it can't be solved with a linear program. The problem is that the linear program's premise is that once we reach the edge of a convex surface in the direction of optimality, we know for certain it is optimal. With a concavity, this no longer works and the algorithm falls flat. The negative values are like these concavities, they introduce local extrema making it harder to find the global one.

$\endgroup$
  • $\begingroup$ Yes! Good point. This probably matches the OP's question best. $\endgroup$ – Michal Jun 24 '12 at 3:32
  • 1
    $\begingroup$ @Michal: The answer just avoids the point why the modification doesn't work. Not the best IMO. $\endgroup$ – nhahtdh Jun 24 '12 at 3:32
  • $\begingroup$ @nhahtdh I agree I don't go into detail, but I'm not avoiding why it doesn't work, this is exactly what I'm addressing and it is a simple principle. It doesn't work since greedy algorithms never reconsider their choices and assume optimality at every step of the algorithm. Negative edges would require look-aheads and thus do not work with greedy algorithms. $\endgroup$ – Gustav Larsson Jun 24 '12 at 3:48
  • $\begingroup$ @GustavLarsson: I'm thinking of the modification as a separate algorithm, and I want to see why the modification doesn't work. I will be more convinced if I see a case that the algorithm doesn't work (except for the obvious negative cycle case). $\endgroup$ – nhahtdh Jun 24 '12 at 3:56
  • 1
    $\begingroup$ The point about greedy is the assumption "more edges can not yield a shorter path" which is violated if you allow negative edges. $\endgroup$ – Raphael Jun 26 '12 at 16:21
4
$\begingroup$

Yes, not deleting the node is the obvious and accepted solution to negative edges. The trick here is that for whatever historical reasons, and as part of a diabolical scheme to better confuse you, we use a different name for this modified algorithm*:

Bellman-Ford algorithm.

*ok, there are some caveats but I'm trying to just gloss over things here...

The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph. For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem. Thus, Bellman–Ford is used primarily for graphs with negative edge weights. The algorithm is named after its developers, Richard Bellman and Lester Ford, Jr.

If a graph contains a "negative cycle", i.e., a cycle whose edges sum to a negative value, then walks of arbitrarily low weight can be constructed by repeatedly following the cycle, so there may not be a shortest path. Bellman-Ford can detect negative cycles and report their existence, but it cannot produce a correct answer if a negative cycle is reachable from the source.[1]


Caveats: As pointed out by nhahtdh in the comments, you need to keep in mind that, if negative edges are allowed, then it might be possible for infinite negative loops to exist and if that is the case, there might be no minimal length path. If someone is not mentioning negative edges to you its likely because they don't want to bother with this kind of detail.

Also, as pointed out by JeffE in the comments, although the basic "relaxation" step is the same in both algorithms, the optimization using the priority queue doesn't really apply when there are negative edges and it can actually turn out to be counterproductive.

$\endgroup$
  • $\begingroup$ I don't think Bellman-Ford algorithm is like that, though. If you don't delete the node, the algorithm may end up in inf. loop on graph with negative cycle. Bellman-Ford guarantees termination for all graphs. $\endgroup$ – nhahtdh Jun 24 '12 at 3:31
  • $\begingroup$ nhahtdh: Bellman-ford doesn't do anything fancy to avoid infinite loops though - just a couple of straightfoward checks. Other then this detail, its very similar in spirit to Djikstra's algorithm. $\endgroup$ – hugomg Jun 24 '12 at 3:36
  • $\begingroup$ I know that it doesn't do anything fancy, just that the modification to Dijkstra algorithm doesn't work for negative cycle graph. I am not too sure whether it will work for non-negative cycle graph. $\endgroup$ – nhahtdh Jun 24 '12 at 3:37
  • $\begingroup$ @nhahtdh: You are kind of right now that I think of it. $\endgroup$ – hugomg Jun 24 '12 at 3:41
  • 3
    $\begingroup$ No, that's not Bellman-Ford. It's similar, but it's not the same. If you modify Dijkstra's algorithm to reinsert nodes into the priority queue whenever their distance decreases, the resulting algorithm can take exponential time for graphs with negative edges, even when there are no negative cycles. But Bellman-Ford always runs in polynomial time. See these notes for more details. $\endgroup$ – JeffE Jun 25 '12 at 13:22
3
$\begingroup$

A slight variant to Dijkstra algorithm will work on a graph with negative weight, without negative cycle (Competitive Programming 2, Steven Halim). For a general graph (which may contain negative cycle), use Bellman-Ford algorithm, which has fixed time complexity of O(VE), but guarantees termination, and allow detection of negative cycle (we detects the negative cycle, since the shortest path is ill-defined in this case).

We can categorize nodes in Dijkstra's algorithm into 3 types of nodes: processed (whose value will never change), unprocessed (has non-infinity value, but may change), and unreached (whose value is infinity, since we haven't reached the node). In the pseudocode for Dijkstra algorithm on Wikipedia (original?), relax operation is never called on processed node.

A variant to Dijkstra's algorithm will only store the unprocessed nodes in a data structure for "get-min" and "update" operation, and pop out node to process it. It will relax all neighbors of the node alike, and push/modify whichever node whose distance is improved back to the data structure. In this way, the processed node can be reverted to an unprocessed node, and its neighbors will be updated again when it is popped out. The method is correct, since changes to the current best value of a node is always propagated.

The complexity of the variant on any non-negative-cycle graph is in the worst case is exponential time, since it allows reevaluation of the vertices. The actual run-time of the variant is dependent on the data. In the original version, each vertex is only popped out once, while in this variant, a vertex might be popped out more than once.

There is no difference is time complexity if the variant is run on a positive weighted graph.

$\endgroup$
  • $\begingroup$ According to problem no. 3 in the below notes, the generalized Dijkstra can have exponential worst case complexity compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/… Also in the variant, you can't terminate the algorithm early once a goal node is reached, you have to wait until the queue is completely empty as a shorter path might come along after traversing a negative weight edge $\endgroup$ – Paul Dixon Jul 16 '12 at 1:48
  • $\begingroup$ @PaulDixon: Hasn't this mentioned by JeffE comment on missing no's post? $\endgroup$ – nhahtdh Jul 16 '12 at 1:53
1
$\begingroup$

For directed negative edges: Since a negative edge makes that distance appear shorter, the true shortest path could end up not being given as the answer. Hence the problem.

For non-directed negative edges: You could enter an infinite loop trying find the "shortest path" as the negative edge creates a distance that goes to negative infinity.

This occurs because Djikstra's algorithm is a greedy algorithm, as Gustav mentions in another answer here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy