How does Dijkstra's algorithm find the shortest path from a source to every other node?
You keep the best known distance to every node, and you always work on the node whose best distance is the smallest.
import heapq
def dijkstra(graph, start):
distance = {start: 0}
heap = [(0, start)]
while heap:
current_distance, node = heapq.heappop(heap)
if current_distance > distance.get(node, float("inf")):
continue
for neighbour, weight in graph[node].items():
new_distance = current_distance + weight
if new_distance < distance.get(neighbour, float("inf")):
distance[neighbour] = new_distance
heapq.heappush(heap, (new_distance, neighbour))
return distance
So how does it work? The heap holds the nodes you have a distance for, and it is sorted by that distance. You take the one with the smallest distance, and then you look at its neighbours. For each neighbour you work out the distance through the current node, and if that is smaller than what you had before then you update it and put it in the heap.
And the key idea is that the node with the smallest distance is finished. There is no shorter route to it, because any route that went through another node would have to go through a node with a smaller distance first, and that one would have been done already.
the graph the edges and their weights
A -> B (4) A to B costs 4
A -> C (1) A to C costs 1
C -> B (2) C to B costs 2
the distances from A
A is 0
C is 1, because it comes first
B is 3, because you go A to C to B
And the check if current_distance > distance.get(node, ...) is what handles the old entries in the heap. When you find a shorter route to a node you put it in the heap again, so the heap can hold two entries for the same node. The old one is ignored when it comes out, because a better distance is already known.
And the complexity is O of n plus m times the log of n for the time, and O of n plus m for the space.
And there is one condition that matters. All the edge weights have to be positive, or at least not negative. With a negative edge the algorithm can give a wrong answer, because the finished node might later get a shorter route.
So the rule to remember is this. Always work on the node with the smallest distance, and the weights must not be negative.
The next two questions in this topic show the version without a heap and the version that returns the path.