Triple loop
- Algorithms course
- Advanced
- Lesson 26/56
- 4 min
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.
Practice 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)).
Starter code
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 relaxationSample 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))Expected output
4
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Outer loop variable
for ____ in range(n):for k in range(n):Explanation: k is right.
2 What is the complexity of the triple loop?
- O(n²)
- O(n³) Correct answer
- O(n log n)
- O(n)
Explanation: Three nested loops give O(n³).
3 Triple loop: match the terms
| Term | Meaning |
|---|---|
k |
Intermediate |
i |
Start |
j |
End |
n |
Node count |