Relaxation
- Algorithms course
- Advanced
- Lesson 31/56
- 4 min
Relax edges when a shorter path is found.
Relaxation
When a node is picked, its neighbors are relaxed: dist[v] = min(dist[v], dist[u] + w). If a shorter path from u to v is found, the distance is updated.
This operation is done at most once per edge. Relaxation is the core step of Dijkstra.
Loop structure
Dijkstra runs in a loop: each round picks the unvisited node with smallest distance, then relaxes its neighbors. It ends when all nodes are visited.
This structure lets the algorithm fix one node per round. Complexity is O(n²).
Practice dijkstra function
Write dijkstra(graph, src). Each round pick the smallest unvisited node, relax neighbors. Print [0, 3, 1, 4] with print(dijkstra(init_graph(), 0)).
Starter code
def init_graph():
# Return adjacency list
return [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], []]
def dijkstra(graph, src):
# Find single-source shortest pathsSample solution
def init_graph():
# Return adjacency list
return [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], []]
def dijkstra(graph, src):
# Find single-source shortest paths
n = len(graph)
dist = [float('inf')] * n
dist[src] = 0
visited = [False] * n
for _ in range(n):
u = -1
best = float('inf')
for i in range(n):
if not visited[i] and dist[i] < best:
best = dist[i]
u = i
if u == -1:
break
visited[u] = True
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return dist
print(dijkstra(init_graph(), 0))Expected output
[0, 3, 1, 4]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Relaxation: match the terms
| Term | Meaning |
|---|---|
dist[u] |
Source distance |
w |
Edge weight |
dist[v] |
Target distance |
min |
Smaller |
2 What is the shortest distance from 0 to 3?
- 5
- 6
- 4 Correct answer
- 1
Explanation: Path 0→2→1→3 gives 1+2+1=4.
3 Relaxation condition
if dist[u] + w ____ dist[v]:if dist[u] + w < dist[v]:Explanation: < is right.