Edge relaxation loop

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.

Exercise relax function

Write relax(dist, u, v, w). If dist[u] + w < dist[v], update dist[v]. Print 4 with print(dist[1]).

Show example 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])

Test yourself

Outer loop count

for _ in range(n - ____):

Show answer

for _ in range(n - 1):

How many times does the outer loop run for n=4?
- 4
- 3
- 5
- 1
Show answer

3 — n-1 = 4-1 = 3 times.
Edge relaxation loop: match the terms

n-1

Pass count
m

Edge count
dist[u]

Source
dist[v]

Target

Next lesson: Negative cycle

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies