Relaxation

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²).

Exercise 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)).

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

Test yourself

Relaxation: match the terms

dist[u]

Source distance
w

Edge weight
dist[v]

Target distance
min

Smaller
What is the shortest distance from 0 to 3?
- 5
- 6
- 4
- 1
Show answer

4 — Path 0→2→1→3 gives 1+2+1=4.

Relaxation condition

if dist[u] + w ____ dist[v]:

Show answer

if dist[u] + w < dist[v]:

Next lesson: Summary - Dijkstra

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies