Edge relaxation loop
- Algorithms course
- Advanced
- Lesson 34/56
- 4 min
Relax all edges V-1 times.
Edge relaxation loop
Bellman-Ford traverses all edges n-1 times. Each pass relaxes every edge once. Total (n-1)·m relaxations are done.
Each pass covers paths of at least one more edge length. n-1 passes guarantee the longest possible path.
Relaxation step
For each edge: if dist[u] + w < dist[v]: dist[v] = dist[u] + w. If a shorter path through u to v exists, it is updated.
This simple check is the heart of the algorithm. It is repeated for each edge.
Practice relax function
Write relax(dist, u, v, w). If dist[u] + w < dist[v], update dist[v]. Print 4 with print(dist[1]).
Starter code
dist = [0, float('inf'), float('inf'), float('inf')]
def relax(dist, u, v, w):
# Relax one edgeSample solution
dist = [0, float('inf'), float('inf'), float('inf')]
def relax(dist, u, v, w):
# Relax one edge
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
relax(dist, 0, 1, 4)
print(dist[1])Expected output
4
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Outer loop count
Question
for _ in range(n - ____):
Answer
for _ in range(n - 1):Explanation: 1 is right.
2 How many times does the outer loop run for n=4?
- 4
- 3 Correct answer
- 5
- 1
Explanation: n-1 = 4-1 = 3 times.
3 Edge relaxation loop: match the terms
| Term | Meaning |
|---|---|
n-1 |
Pass count |
m |
Edge count |
dist[u] |
Source |
dist[v] |
Target |