Card 09/ 11
Running Dijkstra's Algorithm on a Negative Edge
A vertex settled early is never looked at again, so a cheaper route that arrives later through a negative edge is lost.
Dijkstra's algorithm gives wrong distances on a graph with a negative edge, without any error or warning. This card runs it and Bellman-Ford on one small graph, shows where the wrong distance comes from, and says what to use instead.
The symptom is a distance that is too large: a cheaper route exists and the program never reports it. The trigger is a negative weight, such as a rebate, a refund or a gain, on an edge into a vertex the algorithm has already settled. The graph below has one.
A run gave both algorithms the graph from A. The table puts their distances side by side.
| Vertex | Dijkstra's algorithm | Bellman-Ford | The shortest path |
|---|---|---|---|
| A | 0 | 0 | A |
| B | 2 | 1 | A C D B, costing 3 + 1 − 3 |
| C | 3 | 3 | A C |
| D | 4 | 4 | A C D |
| E | 5 | 4 | A C D B E |
The mechanism is the order of settling. Dijkstra's algorithm settles A, then B at 2, because 2 is the smallest distance in the queue, and relaxes B->E to give E 5. It settles C at 3 and D at 4. Only then does it look at D->B, which offers B a distance of 4 − 3 = 1, but B is settled and is never looked at again, so neither B nor E is corrected. Settling B at 2 was a promise that no route could do better, and the promise rested on every later edge adding to a path's length. A negative edge breaks it.
The cost is a wrong answer that looks right. The program finishes, every vertex has a distance, and nothing says two of them are too large. A version that does reopen settled vertices gets this graph right, but can take exponential time on others, and still fails on a negative cycle.
The remedy is to check the weights before choosing. If any weight is negative, use Bellman-Ford, which made every distance right here because it never settles anything early, and which reports a negative cycle if one exists. The listing below is the run behind the table.
import heapq
import math
def dijkstra(vertices, edges, source):
graph = {v: [] for v in vertices}
for u, v, w in edges:
graph[u].append((v, w))
dist = {v: math.inf for v in vertices}
dist[source] = 0
settled, queue, order = set(), [(0, source)], []
while queue:
_, u = heapq.heappop(queue)
if u in settled:
continue
settled.add(u)
order.append(u)
for v, w in graph[u]:
if v not in settled and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(queue, (dist[v], v))
return dist, order
def bellman_ford(vertices, edges, source):
dist = {v: math.inf for v in vertices}
dist[source] = 0
for _ in range(len(vertices) - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return dist
V = ["A", "B", "C", "D", "E"]
EDGES = [("A", "B", 2), ("A", "C", 3), ("C", "D", 1), ("D", "B", -3), ("B", "E", 3)]
d, order = dijkstra(V, EDGES, "A")
print("dijkstra settles:", " ".join(order))
print("dijkstra: ", ", ".join(f"{v} {d[v]}" for v in V))
b = bellman_ford(V, EDGES, "A")
print("bellman-ford: ", ", ".join(f"{v} {b[v]}" for v in V))dijkstra settles: A B C D E
dijkstra: A 0, B 2, C 3, D 4, E 5
bellman-ford: A 0, B 1, C 3, D 4, E 4← → move through sections and cards