Priority queue
- Algorithms course
- Advanced
- Lesson 30/56
- 4 min
Dijkstra uses a priority queue efficiently.
Priority queue
Dijkstra picks the unvisited node with the smallest distance at each step. This selection is sped up with a priority queue.
In a basic implementation, linear search also works: we scan all unvisited nodes and find the smallest dist.
Initial state
All node distances are initialized to inf, except dist[src] = 0. The visited array fills with False.
This initial state lets the algorithm spread step by step from the single source.
Practice init_dist function
Write init_dist(n, src). Return an array filled with float('inf'), set dist[src] = 0. Print it with print(init_dist(4, 0)).
Starter code
def init_dist(n, src):
# Return initial distance arraySample solution
def init_dist(n, src):
# Return initial distance array
dist = [float('inf')] * n
dist[src] = 0
return dist
print(init_dist(4, 0))Expected output
[0, inf, inf, inf]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Initial distance
dist[src] = ____dist[src] = 0Explanation: 0 is right.
2 What is dist[src] at the start?
- inf
- 0 Correct answer
- 1
- -1
Explanation: dist[src] = 0 is the initial value.
3 Priority queue: match the terms
| Term | Meaning |
|---|---|
dist[src] |
0 |
dist[i] |
inf |
visited |
False |
n |
Node count |