Graphs6 min read

Dijkstra's Algorithm

GPS for graphs — find the cheapest route from one node to all others

time with heap: \(O((V+E)\) log V)time with array: \(O(V^2)\)space: \(O(V)\)

BFS finds the shortest path when all roads cost the same. But what about a real map where roads have different travel times? You need Dijkstra's algorithm.

Think of it like a GPS. It knows all the road speeds and continuously picks the fastest next road — always choosing the route that gets you there soonest. Dijkstra works on graphs with non-negative edge weights. For negative weights, use Bellman-Ford.

The core idea: always settle the cheapest node next

Keep a distance table — infinity for every node except the start (distance 0). Use a min-heap to always process the node with the lowest known cost. When you process a node, check whether any of its neighbors can be reached more cheaply through it. If yes, relax (update) their distance.

pseudocode

function dijkstra(graph, start):
  dist = { all nodes: Infinity }
  dist[start] = 0
  heap = MinHeap()
  heap.push([0, start])

  while heap not empty:
    [d, node] = heap.pop()
    if d > dist[node]: continue  // stale entry

    for [neighbor, weight] of graph[node]:
      newDist = dist[node] + weight
      if newDist < dist[neighbor]:
        dist[neighbor] = newDist
        heap.push([newDist, neighbor])

  return dist

◈ Watch nodes get settled one by one and the distance table update in real time

← → arrow keys to step · click elements to interact

Dijkstra's Algorithm

import heapq

def dijkstra(graph, src):
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
print(dijkstra(graph, 'A'))

Output

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

Why the greedy approach works

Because all edge weights are non-negative, once a node is popped from the min-heap with distance d, no shorter path to that node can be discovered later. Any later path must go through nodes with equal or greater distances — only adding more cost. This guarantee makes the algorithm correct.

Reconstructing the path

Keep a prev table: whenever you relax a neighbor through the current node, record prev[neighbor] = current. Walk backward from the destination through prev to reconstruct the full route.

Heap vs plain array

With a min-heap: \(O((V+E)\) log V). With a plain array (scan for minimum each step): \(O(V^2)\). For sparse graphs the heap wins; for very dense graphs the difference narrows.

Note: Dijkstra fails with negative edge weights. A negative edge could make a longer-looking path cheaper after a node is already settled — breaking the correctness guarantee. Use Bellman-Ford for negative weights.

Complexity

Time (min-heap)Heap extract + edge relaxation

Efficient\(O((V+E)\) log V)

Time (plain array)Linear scan for minimum each step

Simple\(O(V^2)\)

SpaceDistance table, prev table, heap

Linear\(O(V)\)

Shortest Path with Route Reconstruction

import heapq

def shortest_path(graph, src, dst):
    dist = {n: float('inf') for n in graph}
    prev = {n: None for n in graph}
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    path, cur = [], dst
    while cur: path.append(cur); cur = prev[cur]
    return dist[dst], list(reversed(path))

graph = {'A':[('B',1),('C',4)],'B':[('C',2),('D',5)],'C':[('D',1)],'D':[]}
d, path = shortest_path(graph, 'A', 'D')
print(d, path)

Output

4 ['A', 'B', 'C', 'D']

Challenge

Quick check

Node B is popped from Dijkstra's min-heap with distance 5. Later, another entry for B appears with distance 8. What happens?

Breadth-First Search

Explore a city map ring by ring — nearest neighbors first

→

Bellman-Ford Algorithm

Shortest paths with negative weights — and negative cycle detection

→

Minimum Spanning Tree

Connect all cities with the least total road construction cost

→

Floyd-Warshall Algorithm

All-pairs shortest paths in one elegant triple loop

→