🎓 A1Learner
🔍

DSA Dijkstra's Algorithm

Dijkstra's algorithm is a method that finds the cheapest route from one start node to every node. It settles nodes in rising order of their best known cost.

One relaxation step

Relaxing edge C to B tests the route through C. The candidate 2 plus 1 beats the stored 4.

dist = {"B": 4}
candidate = 2 + 1
if candidate < dist["B"]:
    dist["B"] = candidate
print(dist)

The heap orders by distance then node

Pairs compare on distance first and node second. Equal distances therefore leave in label order.

import heapq
heap = []
heapq.heappush(heap, (5, "D"))
heapq.heappush(heap, (3, "B"))
heapq.heappush(heap, (3, "A"))
print(heapq.heappop(heap))
print(heapq.heappop(heap))

Example

import heapq

graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("C", 1), ("D", 5)],
    "C": [("A", 2), ("B", 1), ("D", 8), ("E", 10)],
    "D": [("B", 5), ("C", 8), ("E", 2)],
    "E": [("C", 10), ("D", 2)],
}

def dijkstra(graph, start):
    dist = {node: None for node in graph}
    dist[start] = 0
    heap = [(0, start)]
    settled = []
    relaxations = 0
    pushes = 1
    while heap:
        d, node = heapq.heappop(heap)
        if dist[node] is not None and d > dist[node]:
            continue
        settled.append(node)
        for nxt, w in graph[node]:
            relaxations += 1
            cand = d + w
            if dist[nxt] is None or cand < dist[nxt]:
                dist[nxt] = cand
                heapq.heappush(heap, (cand, nxt))
                pushes += 1
    return dist, settled, relaxations, pushes

dist, settled, relaxations, pushes = dijkstra(graph, "A")
for node in sorted(dist):
    print(node, dist[node])
print("settled order:", settled)
print("relaxations:", relaxations)
print("pushes:", pushes)

Key points

  • Relaxation is testing whether one edge improves a known distance
  • A tentative distance is the best cost found for a node so far
  • A settled node is a node whose cheapest distance is final
  • The heap holds pairs of distance first and node second
  • Equal distances resolve by node label because the heap compares pairs

In this example, the heap settles A first and then C at distance 2. Relaxing through C drops B from 4 to 3. B then settles and opens D at distance 8. D opens E at distance 10, beating the direct edge from C. The settled order and the sorted distance table are both printed. The counts show 14 relaxations and 8 pushes for this map.

Note

Dijkstra needs every edge weight to be zero or positive.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

In Dijkstra's algorithm, what does one relaxation do?