Triple loop

Nested k, i, j loops update the table.

Triple loop

The algorithm runs three nested loops: the outer loop is the intermediate node k, the two inner loops traverse i and j. Complexity is O(n³).

For each k, all (i, j) pairs are tried and the matrix is updated. This structure relaxes all pairs.

Intermediate node

k is the node used as a stopover when going from i to j. If the path i → k → j is shorter than the direct i → j, the distance is updated.

This tries all possible intermediate nodes to find the shortest path. The algorithm updates the table once for each k.

Exercise relax_edge function

Write relax_edge(dist, i, j, k). Return min(dist[i][j], dist[i][k] + dist[k][j]). Print 4 with print(relax_edge(init_graph(), 0, 2, 1)).

Show example solution

def init_graph():
    # Return adjacency matrix
    return [[0, 3, 999, 7], [999, 0, 1, 999], [999, 999, 0, 2], [999, 4, 999, 0]]
def relax_edge(dist, i, j, k):
    # Perform one relaxation
    return min(dist[i][j], dist[i][k] + dist[k][j])
print(relax_edge(init_graph(), 0, 2, 1))

Test yourself

Outer loop variable
```
for ____ in range(n):
```
Show answer
```
for k in range(n):
```
What is the complexity of the triple loop?
- O(n²)
- O(n³)
- O(n log n)
- O(n)
Show answer

O(n³) — Three nested loops give O(n³).
Triple loop: match the terms

k

Intermediate
i

Start
j

End
n

Node count

Next lesson: Table update

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies