Dijkstra's Algorithm

You want to drive from your home, A, to a friend's place, F. The map shows six places and the minutes each road takes. One route uses only 3 roads: A → B → E → F. It takes 6 + 5 + 2 = 13 minutes. Another route uses 5 roads, A → C → B → D → E → F, and takes only 2 + 3 + 2 + 1 + 2 = 10 minutes.

BFS would hand you the 3-road route, because it counts roads, not minutes. When edges have weights, you need a search that spreads out by total cost instead of by number of edges. That is Dijkstra's algorithm.

#The idea: settle the closest place first

Keep a best-known distance for every place. At the start, the start is 0 and everything else is ∞, meaning "no route found yet". Then repeat two moves:

1. Settle the unfinished place with the smallest known distance. Its distance is now final.
2. Relax its roads: for each neighbour, check whether going through this place is cheaper than the neighbour's best-known distance. If it is, lower it.

Here is why you can trust the smallest one. Say C is the closest unfinished place at 2 minutes. Any other route to C would have to leave the settled area through some other unfinished place first, and every one of those is already at least 2 minutes away. Roads cannot take negative time, so the detour can only add minutes. Nothing can beat 2.

To find the smallest unfinished distance quickly, keep the candidates in a min-heap, as in Heaps and Priority Queues. Each entry is a pair: (distance, place).

#Trace it on the map

Green places are settled. The number under each place is its best-known distance. Watch B: it gets a distance early, then a better one, and the heap is left holding an out-of-date entry.

dist[start] = 0; push (0, start)while heap is not empty:  (d, node) = pop smallest  if d > dist[node]: skip (stale)  for each (next, w) of node's roads:    if d + w < dist[next]:      dist[next] = d + w      push (d + w, next)

#Stale entries

When B dropped from 6 to 5, the entry 6 B was already inside the heap. A binary heap has no cheap way to find it and change it. So the code does the simple thing: it pushes a new entry, 5 B, and leaves the old one where it is.

The smaller entry always comes out first, so B is settled at 5. When 6 B finally comes out, the check d > dist[node] spots that it is out of date and skips it. In the trace, 4 of the 10 pops were stale. That is wasted work, but only a little, and it keeps the code short.

#The code

The graph is an adjacency list as in Graph Basics, except each neighbour comes with its road's cost. In JavaScript, copy heapPush and heapPop from the heaps lesson and make one change: in each comparison, compare the first items, so heap[parent] <= heap[i] becomes heap[parent][0] <= heap[i][0]. Pairs are then ordered by distance. Python's heapq already orders tuples by their first item.

// graph: { A: [["B", 6], ["C", 2]], ... }  place -> list of [neighbour, cost]
// Every place needs a list, even an empty one.
// heapPush / heapPop: the min-heap from the heaps lesson, comparing item[0]
function dijkstra(graph, start) {
  const dist = { [start]: 0 };
  const parent = { [start]: null };
  const heap = [[0, start]]; // [distance so far, place]
  while (heap.length > 0) {
    const [d, node] = heapPop(heap);
    if (d > dist[node]) continue; // stale entry: a shorter route was found
    for (const [next, cost] of graph[node]) {
      const newDist = d + cost;
      if (!(next in dist) || newDist < dist[next]) {
        dist[next] = newDist;
        parent[next] = node;
        heapPush(heap, [newDist, next]);
      }
    }
  }
  return { dist, parent };
}
// dijkstra(graph, "A").dist → { A: 0, B: 5, C: 2, D: 7, E: 8, F: 10 }

import heapq
 
# graph: {"A": [("B", 6), ("C", 2)], ...}  place -> list of (neighbour, cost)
# Every place needs a list, even an empty one.
def dijkstra(graph, start):
    dist = {start: 0}
    parent = {start: None}
    heap = [(0, start)]  # (distance so far, place)
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue  # stale entry: a shorter route was found
        for nxt, cost in graph[node]:
            new_dist = d + cost
            if nxt not in dist or new_dist < dist[nxt]:
                dist[nxt] = new_dist
                parent[nxt] = node
                heapq.heappush(heap, (new_dist, nxt))
    return dist, parent
 
# dijkstra(graph, "A")[0] → {'A': 0, 'B': 5, 'C': 2, 'D': 7, 'E': 8, 'F': 10}

A place missing from dist at the end cannot be reached. The parent map works exactly like the one in BFS: start at the goal, follow parents back to the start, and reverse. If you only need the route to one goal, you can stop as soon as the goal is popped, because that is the moment its distance becomes final.

#Common mistakes

#Check yourself

#What to practise next

When some costs are negative, or you need the distance between every pair of places, move on to Bellman-Ford and Floyd-Warshall. You will see Dijkstra's shape again in Prim's algorithm in Minimum Spanning Trees, with one key change.