8
$\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$
  • $\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
  • 1
    $\begingroup$ @nhahtdh What if you marked a node as processed but didn't delete it from the graph? This would prevent it from being repetitively processed but allow it to be updated. In your example of the first node being 0, after it's processes it would be marked to prevent repetitive processing. However since its not deleted a shorter path can be updated later on. Wouldn't this work? $\endgroup$ – user1422 Jun 25 '12 at 3:01
  • 1
    $\begingroup$ @nhahtdh That seems like a valid algorithm. I would assume it would take around the same amount of time as Dijkstra's algorithm. Do you see any reason why it wouldn't work? $\endgroup$ – user1422 Jun 25 '12 at 3:36
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.

| cite | improve this answer | |
$\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
5
$\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.

| cite | improve this answer | |
$\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
4
$\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.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

For Dijkstra's Algorithm, at every step, the visited node, v, is done and never visited again (invariant) , the edge to that node v is the min edge.

To show why Dijkstra's Algorithm would not produce a optimized shortest path, let's take this graph with negative edge (A, B) as an example, at the start there are S (source node), A, B, C, D.

  1. Starting at source node S, we would choose the edge (S, B) as the edge weight is shorter.

  2. Node is would be marked done and the edge (S, B) would be set as the min edge from S to B.

  3. Since Dijkstra is a greedy Algorithm, node B is visited and would never be visited again.

But there is a shorter path from S -> A -> B of weight 0. Dijkstra would provide a wrong path since it might not be considered due to the invariant of the algo.

Graph of Negative weight edges

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?

It would be slower, keep it only if you need to. If you do that, you are essentially writing the Bellman Ford Algorithm, so I would refer address it as the Bellman Ford Algorithm. It is the original shortest path algorithm. Assume a graph of V vertices and E edges. Note that Dijkstra $ O((V + E) log V) $, is slightly faster than Bellman Ford $ O (VE) $, as it is a optimized version of Bellman Ford.

i. Dijkstra is faster than Bellman Ford due to it's invariant. It would only visit each vertex once and the edges it checks would reduce as vertex visited increases, since it assumes the edges it sets would be the best path. Whereas,

ii. Bellman Ford algorithm would run the relax function for V times on E edges. It works by overestimating the length of the path from the starting vertex to all other vertices. Then it iteratively relaxes those estimates by finding new paths that are shorter than the previously overestimated path. After 1 iteration of relaxing E edges, one edges is the best path.

So if you correctly tweak the program to keep the edge, it would be slower. In algorithm, you often have to trade time and function, time and space, it depends on you.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ "It would then become Bellman-Ford." I can only upvote this answer if that proposition is explained clearly. It is unlikely it would become Bellman-Ford. $\endgroup$ – John L. May 2 at 14:29
  • $\begingroup$ cs.stackexchange.com/questions/2482/… $\endgroup$ – D.W. May 3 at 6:09
  • $\begingroup$ @D.W. it is not a repeat as the post only briefly explained what Dijkstra is, but did not say explain how greedy algo would not suffice. I also addressed the point that the OP was mentioning was actually Bellman Ford and elaborated why it is Bellman Ford $\endgroup$ – Peter May 3 at 7:37

Your Answer

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