Challenge 3
- Algorithms course
- Advanced
- Lesson 55/56
- 4 min
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.
Practice 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)).
Starter code
def shortest_distance(graph, src, dst):
# Find src→dst distance with DijkstraSample 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))Expected output
4
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Challenge 3: match the terms
| Term | Meaning |
|---|---|
0→1 |
2 |
0→2 |
3 |
1→3 |
6 |
0→3 |
4 |
2 Smallest pick
Question
if not visited[i] and dist[i] ____ best:
Answer
if not visited[i] and dist[i] < best:Explanation: < is right.
3 Which is the shortest path from 0 to 3?
- 0→3 (direct)
- 0→1→3
- 0→1→2→3 Correct answer
- 0→2→3
Explanation: Path 0→1→2→3 gives 2+1+1=4.