Using Dijkstra's algorithm with negative edges?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

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.