Bellman-Ford algorithm
Shortest paths from a source with arbitrary weights: passes that relax every arc, the table pass after pass, early stop, detecting a negative-weight cycle, the cost and the link with distance-vector routing.
- 24 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Pass: what is it?
Show the answer
One full round of the Bellman-Ford algorithm, during which every arc of the graph is examined once.
After pass k, the distance of every vertex that has a shortest path of at most k arcs is exact. That is why n − 1 passes suffice: a simple path has at most n − 1 arcs.
This program relaxes the arcs in the order of the list, for only two passes. What does it print?
```python
arcs = [("C", "D", 2), ("B", "C", -3), ("A", "B", 5), ("S", "A", 4), ("S", "C", 10)]
dist = {v: float("inf") for v in "SABCD"}
dist["S"] = 0
for _ in range(2):
for u, v, w in arcs:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
print(dist)`{'S': 0, 'A': 4, 'B': 9, 'C': 10, 'D': 12}{'S': 0, 'A': 4, 'B': 9, 'C': 6, 'D': 8}{'S': 0, 'A': 4, 'B': inf, 'C': 10, 'D': inf}{'S': 0, 'A': 4, 'B': 9, 'C': 6, 'D': 12}
Show the answer
{'S': 0, 'A': 4, 'B': 9, 'C': 10, 'D': 12}In pass 1 only A (4) and C (10) are reached, because the arcs are examined in an unfavourable order. In pass 2, D = 12 (through C) then B = 9 (through A). C only drops to 6 in pass 3 and D to 8 in pass 4: n − 1 = 4 passes are needed.
In a graph of n vertices with no negative cycle, … passes relaxing every arc are enough to get the shortest paths.
Show the answer
In a graph of n vertices with no negative cycle, n − 1 passes relaxing every arc are enough to get the shortest paths.
A simple shortest path crosses at most n vertices, so n − 1 arcs, and each pass "finishes" at least one more.
Negative-weight cycle: what is it?
Show the answer
A cycle whose weights sum to strictly less than zero: going round it again and again lowers a path's length without limit.
If such a cycle is reachable from the source, there is no shortest path to its vertices: their distance is minus infinity.