Summary - Dijkstra
- Algorithms course
- Advanced
- Lesson 32/56
- 4 min
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.
Practice shortest_path function
Write shortest_path(graph, src, dst). Run Dijkstra, return dist[dst]. Print 4 with print(shortest_path(init_graph(), 0, 3)).
Starter code
def shortest_path(graph, src, dst):
# Find src→dst distance with DijkstraSample 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))Expected output
4
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is the output of Dijkstra?
- Visited array
- A single path
- Edge list
- Distance array Correct answer
Explanation: The output is the distance array from source to all nodes.
2 n assignment
Question
n = len(____)
Answer
n = len(graph)Explanation: graph is right.
3 Summary - Dijkstra: match the terms
| Term | Meaning |
|---|---|
init_graph |
Graph |
init_dist |
Distance |
dijkstra |
Algorithm |
dist |
Output |