Challenge 3

Print shortest distances with Dijkstra.

Challenge 3: Dijkstra

In this challenge you will apply Dijkstra's algorithm on a graph. Find single-source shortest paths and return the distance to a specific target.

Graph: [[(1, 2), (2, 4)], [(2, 1), (3, 5)], [(3, 1)], []]. The shortest distance from 0 to 3 is 4.

Exercise shortest_distance function

Write shortest_distance(graph, src, dst). Run Dijkstra, return dist[dst]. Print 4 with print(shortest_distance([[(1, 2), (2, 4)], [(2, 1), (3, 5)], [(3, 1)], []], 0, 3)).

Show example solution

def shortest_distance(graph, src, dst):
    # Find src→dst distance with Dijkstra
    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[dst]
print(shortest_distance([[(1, 2), (2, 4)], [(2, 1), (3, 5)], [(3, 1)], []], 0, 3))

Test yourself

Challenge 3: match the terms

0→1

2
0→2

3
1→3

6
0→3

4

Smallest pick

if not visited[i] and dist[i] ____ best:

Show answer

if not visited[i] and dist[i] < best:

Which is the shortest path from 0 to 3?
- 0→3 (direct)
- 0→1→3
- 0→1→2→3
- 0→2→3
Show answer

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

Next lesson: Challenge 4

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies