Summary - Dijkstra

Run Dijkstra on a small graph and print distances in a mini task.

Summary - Dijkstra

In this group you learned Dijkstra, which finds shortest paths from a single source to all nodes. Adjacency list, distance array and relaxation combine into the solution.

Now you will write a query function that brings all pieces together. This summary unites the group's concepts in a single piece of code.

Exercise shortest_path function

Write shortest_path(graph, src, dst). Run Dijkstra, return dist[dst]. Print 4 with print(shortest_path(init_graph(), 0, 3)).

Show example solution

def shortest_path(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_path(init_graph(), 0, 3))

Test yourself

What is the output of Dijkstra?
- Visited array
- A single path
- Edge list
- Distance array
Show answer

Distance array — The output is the distance array from source to all nodes.
n assignment
```
n = len(____)
```
Show answer
```
n = len(graph)
```
Summary - Dijkstra: match the terms

init_graph

Graph
init_dist

Distance
dijkstra

Algorithm
dist

Output

Next lesson: Negative weights

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies