CODEWITHSUNDEEP
algorithmrecursiondijkstra
Dan Brenner
Dan Brenner

Reputation: 898

Dijkstra and Negative Edges

I'm having trouble understanding why Dijkstra's algorithm does not work on acyclic directed graphs with negative edges. As I understand it, Dijkstra does a breadth-first traversal of the graph, relaxing when appropriate. For instance, consider the graph:

S->A (3)
S->B (4)
B->A (-2)

Where S is the source node. This is how I imagine it working:

1) Mark A with a distance of 3. Mark B with a distance of 4.

2) Recurse on A. Since A points to no nodes, do nothing.

3) Recurse on B. Since B points to A, check to see if B's distance + B->A is less than the current distance of A. 2 < 3, so mark A with a distance of 2.

Yet apparently this is not how it works, as the book I use gives this very graph to show why negatives DON'T work. I cannot follow the book's explanation. How would Dijkstra work on this graph and why would they not use the method I am imagining?

Upvotes: 1

Views: 701

Answers (1)

G. Bach
G. Bach

Reputation: 3909

The problem is, once you process a node, you cannot afterwards update its distance, since that would require recursive updates and would throw off the whole thing (read: go against the assumption of the algorithm that the nodes are processed in monotonously increasing distance to the source; see the proof of correctness for the algorithm to see where that is required). So once A was processed, you can't later change its distance, which means you can't have negative edges since they might give you shorter distances to previously processed nodes. The assumption of monotonously increasing distances is why you mark nodes black once they have been processed, and you disregard black nodes afterwards. So even though in that graph A would have a distance of 2 to S, Dijkstra's algorithm would give you a distance of 3 since it disregards any edges leading towards A after A was processed.

EDIT: Here's what Dijkstra's algorithm would do:

1) Mark A with a distance of 3, put it into the queue of nodes awaiting processing; Mark B with a distance of 4, put it into the queue.

2) Take A out of the queue since it's at the front. Since A points to no nodes, don't update any distances, don't add anything to the queue. Mark A as processed.

3) Take B out of the queue. B points to A, but A is marked as already processed; ignore the edge B->A. Since there are no more outgoing edges from B, we're done.

EDIT 2: Regarding DAGs, you don't need Dijkstra's algorithm at all. DAGs always have a topological ordering, which can be calculated in O(|V| + |E|), and processing the vertices in the topological order, using d(w) = min {d(w); d(v) + c(v, w)} as the rule for updating distances where d(v) is the distance of vertex v from the source and c(v,w) is the length of edge (v,w) will give you the correct distances, again in O(|V| + |E|). Altogether you have two steps each requiring O(|V| + |E|), so that's the total complexity of calculating single source shortest path in DAGs with arbitrary edge lengths.

Upvotes: 4

Related Questions