Dijkstra's Algorithm

What Is Dijkstra's Algorithm?

Dijkstra's algorithm finds the shortest path from a single source node to all other nodes in a graph with non-negative edge weights (edges where the cost of traversal is zero or positive — never negative). It was created by Dutch computer scientist Edsger W. Dijkstra in 1956. The story goes that he designed it in about 20 minutes while sitting at a café in Amsterdam, thinking about the shortest route between two cities. He didn't even use pencil and paper. He published it three years later and it became one of the most cited algorithms in history.

The key idea: maintain a set of "finalized" nodes whose shortest distance you know for sure. At each step, pick the unfinalized node with the smallest tentative distance (the best distance estimate found so far), finalize it, and update its neighbors. This is a greedy strategy — at each step you make the locally optimal choice. And it works because all edge weights are non-negative, so once you've found the cheapest way to reach a node, no future path can beat it.

Think of it like water spreading outward from a source. The water reaches the closest puddle first, then the next closest, and so on. It never needs to revisit a puddle because water always flows forward.

The "Why No Negative Weights?" Question

Dijkstra assumes that once a node is finalized, its distance can't improve. With negative edges, that assumption crumbles. Imagine a node B finalized with distance 5. Later you discover an edge C→B with weight -10 where C has distance 12. The path through C gives B a distance of 2 — but Dijkstra already locked in 5 and moved on. It'll never correct this.

For graphs with negative weights (but no negative cycles — loops where the total weight is negative, making shortest paths undefined because you can loop forever getting shorter), use Bellman-Ford instead. It's slower — O(V·E) instead of O(E log V) — but handles negatives correctly.

Where Dijkstra Shows Up

• GPS/Maps: Google Maps, Waze, Apple Maps. Finding the fastest route between two points is shortest-path on a road graph where edge weights are travel times.
• Network routing: OSPF (Open Shortest Path First), one of the most widely used interior gateway protocols, runs Dijkstra at every router to build a routing table.
• Game AI: Pathfinding for characters on weighted terrain — different tile types have different movement costs.
• Telecommunications: Minimum-cost routing in phone and data networks.
• Social networks: Finding "closest" connections with weighted relationships (friend-of-friend distance).
• Robotics: Motion planning where different movements have different energy costs.

How It Works

Dijkstra's algorithm is essentially "greedy BFS with a priority queue." Here's the process:

1. Initialize: Set distance to source = 0. Set distance to everything else = ∞ (infinity — meaning "unreachable so far"). Add the source to a min-priority queue (a data structure that always gives you the smallest element first).
2. Extract minimum: Pull the node with the smallest distance from the priority queue. This node is now "finalized" — we're certain about its shortest distance.
3. Relax neighbors: For each neighbor of the current node, compute dist[current] + edge_weight. If that's less than the neighbor's current distance, update it and add (or re-add) the neighbor to the queue.
4. Repeat until the queue is empty (or you've reached your target, if you only care about one destination).

The Relaxation Step

Relaxation is the core operation. It means "I found a potentially better path — let me check." When processing node u and examining its neighbor v:

• If dist[u] + weight(u,v) < dist[v], then the path through u to v is shorter than any path we'd found before
• Update dist[v] = dist[u] + weight(u,v) and record that v's shortest path comes through u (for path reconstruction later)
• The name "relaxation" comes from the idea of "relaxing" a constraint — the triangle inequality (dist[v] ≤ dist[u] + weight(u,v)) gets tighter each time

Priority Queue Choice Matters

The priority queue (also called a min-heap — a tree-based structure where the smallest element is always at the root) is the engine of Dijkstra. Your choice of implementation affects performance:

• Binary heap: O((V + E) log V). Good enough for most practical cases. This is what you'll use in interviews and 99% of production code.
• Fibonacci heap: O(E + V log V). Better asymptotically for dense graphs because decrease-key is O(1) amortized. Rarely used in practice — the constant factors are large and the implementation is complex.
• Simple array scan: O(V²). No heap at all — just scan the array for the minimum each time. Actually better for very dense graphs where E ≈ V², because O(V²) beats O(V² log V).

Path Reconstruction

Dijkstra gives you distances, but often you need the actual path. Keep a predecessor map: when you relax edge u→v, set prev[v] = u. To reconstruct the path to any target, follow the prev pointers backward from target to source, then reverse.

Interactive Visualization

Click a node to set it as the source. Watch Dijkstra work step by step — the algorithm picks the closest unfinalized node, relaxes its neighbors, and updates distances. Finalized nodes turn green, and the current shortest path tree is highlighted.

Common Mistakes

Complexity Analysis

In practice, the binary heap version handles most cases. Here's the breakdown: every node gets extracted from the heap once (V extractions at O(log V) each), and every edge triggers at most one heap insertion (E insertions at O(log V) each). Total: O((V + E) log V). Since E ≥ V-1 for a connected graph, this simplifies to O(E log V) in most discussions.

Comparison with Other Shortest Path Algorithms

*A* performance depends heavily on the heuristic quality. With a perfect heuristic, it finds the answer immediately. With a bad one, it degrades to Dijkstra.

Implementation

Dijkstra with Min-Heap (Standard)

import heapq

def dijkstra(graph, source):
    """Dijkstra's shortest path from source to all reachable nodes.
    
    graph: adjacency list as dict
           {node: [(neighbor, weight), (neighbor, weight), ...]}
    source: starting node
    
    Returns:
        dist: dict mapping each node to its shortest distance from source
        prev: dict mapping each node to its predecessor on the shortest path
              (use reconstruct_path() to get the actual path)
    """
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    prev = {node: None for node in graph}
    
    # Min-heap entries: (distance, node)
    # Python's heapq is a min-heap — smallest element comes out first
    heap = [(0, source)]
    finalized = set()  # Nodes whose shortest distance is confirmed

    while heap:
        d, u = heapq.heappop(heap)

        # Lazy deletion: this entry is stale if we already finalized u
        # (we pushed a duplicate with a shorter distance earlier)
        if u in finalized:
            continue
        finalized.add(u)

        # Relax all neighbors of u
        for v, weight in graph[u]:
            new_dist = d + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(heap, (new_dist, v))

    return dist, prev

def reconstruct_path(prev, target):
    """Walk backwards from target to source using the predecessor map.
    Returns the path as a list from source to target.
    Returns empty list if target is unreachable.
    """
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = prev[node]
    path.reverse()
    # If path starts with source, it's valid; otherwise target was unreachable
    return path

Dijkstra — JavaScript

function dijkstra(graph, source) {
  // graph: { node: [[neighbor, weight], ...] }
  const dist = {};
  const prev = {};
  const finalized = new Set();

  // Initialize all distances to Infinity
  for (const node of Object.keys(graph)) {
    dist[node] = Infinity;
    prev[node] = null;
  }
  dist[source] = 0;

  // Simple priority queue using sorted array
  // (For production code, use a proper min-heap library)
  const pq = [[0, source]];

  while (pq.length > 0) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift();

    if (finalized.has(u)) continue;  // Lazy deletion — skip stale entries
    finalized.add(u);

    for (const [v, weight] of (graph[u] || [])) {
      const newDist = d + weight;
      if (newDist < dist[v]) {
        dist[v] = newDist;
        prev[v] = u;
        pq.push([newDist, v]);
      }
    }
  }
  return { dist, prev };
}

Shortest Path to Specific Target (Early Termination)

import heapq

def dijkstra_target(graph, source, target):
    """Dijkstra with early termination — stops as soon as we finalize target.
    
    This is faster when you only care about one destination, because you
    skip processing all nodes that are farther away than the target.
    """
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    heap = [(0, source)]
    finalized = set()

    while heap:
        d, u = heapq.heappop(heap)
        if u in finalized:
            continue
        finalized.add(u)

        # Once target is finalized, we know its shortest distance for certain
        if u == target:
            return d

        for v, weight in graph[u]:
            new_dist = d + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))

    return float('inf')  # Target unreachable from source

0-1 BFS (When Weights Are Only 0 or 1)

from collections import deque

def bfs_01(graph, source):
    """0-1 BFS: Dijkstra-like shortest path when all weights are 0 or 1.
    
    Uses a deque instead of a heap:
    - 0-weight edges: push neighbor to FRONT (it's equally close)
    - 1-weight edges: push neighbor to BACK (it's one step farther)
    
    This gives O(V + E) time — faster than Dijkstra's O(E log V).
    Perfect for grid problems with "free" vs "costly" moves.
    """
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    dq = deque([source])

    while dq:
        u = dq.popleft()
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)  # Free edge — visit soon
                else:
                    dq.append(v)      # Cost-1 edge — visit later
    return dist

Real-World Example: Network Routing

OSPF (Open Shortest Path First) is one of the most widely deployed routing protocols on the internet. Every OSPF router builds a map of the network (the "link-state database") and runs Dijkstra to compute the shortest path to every other router. That's not metaphorical — the routers literally run Dijkstra's algorithm.

Here's a simplified version showing how a router would compute its routing table:

import heapq

def compute_routing_table(network, my_router):
    """Simulate OSPF-style routing table computation.
    
    network: adjacency list of router connections
             {"R1": [("R2", 10), ("R3", 5)], ...}
             Edge weights represent link costs (based on bandwidth:
             cost = reference_bandwidth / link_bandwidth)
    my_router: this router's ID
    
    Returns: routing table mapping each destination to
             (next_hop, total_cost, full_path)
    """
    # Run Dijkstra from this router
    dist = {r: float('inf') for r in network}
    dist[my_router] = 0
    prev = {r: None for r in network}
    heap = [(0, my_router)]
    finalized = set()

    while heap:
        cost, router = heapq.heappop(heap)
        if router in finalized:
            continue
        finalized.add(router)

        for neighbor, link_cost in network[router]:
            new_cost = cost + link_cost
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                prev[neighbor] = router
                heapq.heappush(heap, (new_cost, neighbor))

    # Build routing table: for each destination, find next hop
    routing_table = {}
    for dest in network:
        if dest == my_router:
            continue
        if dist[dest] == float('inf'):
            continue  # Unreachable
        
        # Trace back from dest to find the first hop after my_router
        path = []
        node = dest
        while node is not None:
            path.append(node)
            node = prev[node]
        path.reverse()
        
        next_hop = path[1] if len(path) > 1 else dest
        routing_table[dest] = {
            "next_hop": next_hop,
            "cost": dist[dest],
            "path": path
        }

    return routing_table

# Example: Small office network
network = {
    "Core":   [("Sales", 10), ("Eng", 5), ("DC", 2)],
    "Sales":  [("Core", 10), ("Guest", 20)],
    "Eng":    [("Core", 5), ("DC", 3), ("Lab", 8)],
    "DC":     [("Core", 2), ("Eng", 3)],
    "Guest":  [("Sales", 20)],
    "Lab":    [("Eng", 8)],
}

table = compute_routing_table(network, "Core")
for dest, info in sorted(table.items()):
    print(f"  To {dest:6s}: via {info['next_hop']:6s} cost={info['cost']:3d}  path={' → '.join(info['path'])}")
# Output:
#   To DC    : via DC     cost=  2  path=Core → DC
#   To Eng   : via Eng    cost=  5  path=Core → Eng
#   To Guest : via Sales  cost= 30  path=Core → Sales → Guest
#   To Lab   : via Eng    cost= 13  path=Core → Eng → Lab
#   To Sales : via Sales  cost= 10  path=Core → Sales

Every time a link goes up or down, OSPF routers flood the change across the network and re-run Dijkstra. On modern hardware, this takes microseconds even for networks with thousands of routers. Dijkstra in production, running billions of times a day across the internet.

Interview Patterns

Common Variations

• Grid shortest path: The "graph" is a matrix, neighbors are adjacent cells, weights are cell values or differences
• K shortest paths: Allow revisiting nodes up to k times. Track (distance, node, stops) in the heap.
• Bidirectional Dijkstra: Run from source and target simultaneously. Stop when frontiers meet. Up to 2× faster in practice on large road networks.
• Max-heap Dijkstra: For "maximum probability path" or "path with maximum minimum edge," flip the heap to a max-heap. Same algorithm, opposite optimization direction.

Practice Problems