Publié · en amélioration
Guide Plus courts chemins et arbres couvrants · 2/6
Ce chapitre n'est disponible qu'en anglais pour le moment.
This chapter traces each algorithm on a small graph so you can see the order of relaxations. The Dijkstra example uses directed edges A→B 4, A→C 1, C→B 2, B→D 1, C→D 5, D→E 3 with source A.
Dijkstra keeps a min-heap of (distance, vertex) pairs. It repeatedly pops the closest vertex; because all weights are non-negative, no later path can make that vertex any cheaper, so its distance is final. It then relaxes the vertex's outgoing edges. When a distance improves we simply push a new pair instead of updating the old one; outdated pairs are skipped when popped ("lazy deletion").
| Pop | A | B | C | D | E | Note |
|---|---|---|---|---|---|---|
| start | 0 | inf | inf | inf | inf | heap: (0,A) |
| (0,A) | 0 | 4 | 1 | inf | inf | push (4,B), (1,C) |
| (1,C) | 0 | 3 | 1 | 6 | inf | B improves 4 to 3 |
| (3,B) | 0 | 3 | 1 | 4 | inf | D improves 6 to 4 |
| (4,B) | 0 | 3 | 1 | 4 | inf | stale, skipped |
| (4,D) | 0 | 3 | 1 | 4 | 7 | push (7,E) |
| (6,D) | 0 | 3 | 1 | 4 | 7 | stale, skipped |
| (7,E) | 0 | 3 | 1 | 4 | 7 | heap empty |
Final distances: A 0, B 3, C 1, D 4, E 7. The shortest path to E is A→C→B→D→E.
Take A→B 2, A→C 3, C→B -2. Dijkstra settles B at distance 2 before it looks at C, but the true distance is 3 + (-2) = 1. The greedy "closest is final" argument assumes that extending a path never makes it shorter, which is false with negative weights. Use Bellman-Ford instead.
Bellman-Ford relaxes every edge, V - 1 times. A shortest path without cycles has at most V - 1 edges, and after round k every path of k edges has been accounted for. One extra round then acts as a test: if any edge can still be relaxed, a negative cycle is reachable from the source.
from math import inf
def bellman_ford(n, edges, source):
dist = [inf] * n
dist[source] = 0
for _ in range(n - 1):
changed = False
for u, v, w in edges:
if dist[u] != inf and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed: # early exit: nothing moved this round
break
for u, v, w in edges:
if dist[u] != inf and dist[u] + w < dist[v]:
raise ValueError("negative cycle reachable from source")
return dist
# S=0, A=1, B=2, C=3
print(bellman_ford(4, [(0, 1, 4), (0, 2, 5), (2, 1, -3), (1, 3, 2)], 0)) # [0, 2, 5, 4]In round 1 the edges are scanned in the listed order: A becomes 4, B becomes 5, then B→A lowers A to 2, and A→C sets C to 4. Round 2 changes nothing, so the loop stops early.
Floyd-Warshall computes all pairs at once with a three-level loop. After processing intermediate vertex k, d[i][j] is the shortest path from i to j that uses only vertices 0..k in between. The order of the loops matters: k must be the outermost.
from math import inf
def floyd_warshall(d):
n = len(d)
for k in range(n):
for i in range(n):
for j in range(n):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
return d
d = [[0, 3, inf], [inf, 0, 1], [2, inf, 0]]
print(floyd_warshall(d)) # [[0, 3, 4], [3, 0, 1], [2, 5, 0]]After the run, a negative value on the diagonal (d[i][i] < 0) means vertex i lies on a negative cycle.
When every weight is 0 or 1, a deque replaces the heap. A vertex reached by a 0-edge goes to the front, by a 1-edge to the back, so the deque always stays sorted by distance and each step is O(1).
from collections import deque
from math import inf
def zero_one_bfs(adj, source):
dist = [inf] * len(adj)
dist[source] = 0
dq = deque([source])
while dq:
u = dq.popleft()
for v, w in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if w == 0:
dq.appendleft(v)
else:
dq.append(v)
return dist
print(zero_one_bfs([[(1, 1), (2, 0)], [(3, 1)], [(1, 0), (3, 1)], []], 0)) # [0, 0, 0, 1]Undirected edges: A-B 1, B-C 2, A-C 3, C-D 4, B-D 5.
| Kruskal (sorted edges) | Decision | Tree weight |
|---|---|---|
| A-B 1 | take, joins two components | 1 |
| B-C 2 | take | 3 |
| A-C 3 | skip, A and C already connected | 3 |
| C-D 4 | take, now V - 1 = 3 edges | 7 |
Prim from A pops the cheapest edge that leaves the tree: A-B 1, then B-C 2 (cheaper than A-C 3), then C-D 4 (cheaper than B-D 5). Both reach the same tree of weight 7. They can pick different trees only when equal weights allow several MSTs, and the total is always the same.
V - 1 rounds; a change in an extra round means a negative cycle.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.