Dijkstra's Algorithm
Shortest routes with a heap.
Dijkstra's algorithm is one of the most famous algorithms ever written. Map apps, network routers, and games all use versions of it. And in Python, with a heap, it's only about a dozen lines.

- One of the most famous algorithms
- Maps, routers, games
- About a dozen lines
Dijkstra in code
The heap holds pairs of distance and place, so heap pop always gives the nearest unexplored place. If we've already found a shorter way to it, we skip it. Otherwise, for each neighbour, we work out the distance through this place. If it beats the best known distance, we record it, and push it onto the heap. Run it. The library is only seven minutes away, through the park, the shop, and the school.
import heapq
from roads import roads
def dijkstra(start):
best = {start: 0}
heap = [(0, start)]
while heap:
dist, place = heapq.heappop(heap)
if dist > best[place]:
continue
for nxt, w in roads[place].items():
new = dist + w
if new < best.get(nxt, float("inf")):
best[nxt] = new
heapq.heappush(heap, (new, nxt))
return best
print(dijkstra("Home")){'Home': 0, 'Shop': 3, 'Park': 1, 'School': 6, 'Library': 7}Also uses roads.py
roads = {
"Home": {"Shop": 4, "Park": 1},
"Park": {"Shop": 2, "School": 6},
"Shop": {"School": 3, "Library": 7},
"School": {"Library": 1},
"Library": {},
}Dijkstra facts
With a heap, Dijkstra runs in O of E log V. It needs every weight to be zero or more. With negative weights, it can give wrong answers, and you'd use a different algorithm, called Bellman Ford. To get the route itself, not just the distance, record each place's parent, just like we did with breadth first search.
| key | value |
|---|---|
| Cost | O(E log V) |
| Needs | no negative weights |
| Negative weights | Bellman-Ford |
| The route | record parents |
Summary
Dijkstra's algorithm uses a heap to always settle the nearest place next. It finds the shortest distances to every place. Next, putting tasks in the right order.
Key takeaways- Heap of (distance, place)
- Relax each edge
- O(E log V)