Shortest Path Algorithms

[!NOTE] Finding the path from A to B is easy. Finding the fastest path is hard. Welcome to the engine behind Google Maps.

1. Dijkstra’s Algorithm (The Greedy Choice)

Dijkstra’s algorithm is the gold standard for finding the shortest path in a graph with non-negative weights.

  • Strategy: Always explore the closest unknown node next. (Greedy).
  • Data Structure: Priority Queue (Min-Heap).
  • Time Complexity: O(E log V).
  • Limitation: Fails if edges have negative weights.

2. The Mathematical Anchor: Dijkstra Correctness

How do we know the greedy choice works?

The Proof by Contradiction

Suppose Dijkstra selects a node u with distance d[u], but there exists a shorter path to u that we haven’t found yet.

  1. This hidden path must pass through some node v currently in the Priority Queue.
  2. Since all weights are non-negative, the distance to v must be ≥ some already “known” distance.
  3. If the path through v was shorter than d[u], v would have been popped from the Priority Queue before u.
  4. Conclusion: By popping the minimum distance from the PQ, we guarantee no shorter path can exist (provided no negative edges “cheat” by reducing total distance later).

3. Hardware Truth: Cache Misses in Large Graphs

In a large social graph with millions of nodes, the Adjacency List implementation becomes a bottleneck for the CPU.

The “Pointer Chasing” Problem

  1. Nodes are stored in a map or array, but their neighbors are stored as separate List objects scattered in RAM.
  2. When BFS/Dijkstra explores neighbors, the CPU must jump to random memory addresses.
  3. Result: Frequent L3 Cache Misses. Even if the algorithm is O(V+E), it may run 5-10x slower on a massive sparse graph than a dense graph stored as a contiguous matrix due to memory latency.

4. Interactive: GPS Navigator

Find the shortest path from Start (Green) to End (Red). The numbers on edges represent travel time (Weight). Click Step to see how Dijkstra explores the map.

Current Node: - | Distance: 0
Priority Queue: []

5. Code Implementation: Dijkstra

Java

public Map<Integer, Integer> dijkstra(int start) {
  // Min-Heap Priority Queue
  PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
  Map<Integer, Integer> distances = new HashMap<>();

  // Init
  for (int i = 0; i < V; i++) distances.put(i, Integer.MAX_VALUE);
  distances.put(start, 0);
  pq.add(new int[]{start, 0});

  while (!pq.isEmpty()) {
    int[] curr = pq.poll();
    int u = curr[0];
    int dist = curr[1];

    if (dist > distances.get(u)) continue;

    for (int v : adj.get(u)) { // Assuming weighted adj
       // In real code, adj would store Pair<Node, Weight>
       int weight = getWeight(u, v);
       if (distances.get(u) + weight < distances.get(v)) {
         distances.put(v, distances.get(u) + weight);
         pq.add(new int[]{v, distances.get(v)});
       }
    }
  }
  return distances;
}

Go

import "container/heap"

// Item is something we manage in a priority queue.
type Item struct {
  node int
  dist int
  index int
}

// PriorityQueue implementation omitted for brevity (standard container/heap)

func Dijkstra(start int, graph map[int]map[int]int) map[int]int {
  dist := make(map[int]int)
  // Init with MaxInt logic...

  pq := make(PriorityQueue, 0)
  heap.Init(&pq)
  heap.Push(&pq, &Item{node: start, dist: 0})
  dist[start] = 0

  for pq.Len() > 0 {
    item := heap.Pop(&pq).(*Item)
    u := item.node

    if item.dist > dist[u] {
      continue
    }

    for v, weight := range graph[u] {
      if alt := dist[u] + weight; alt < dist[v] {
        dist[v] = alt
        heap.Push(&pq, &Item{node: v, dist: alt})
      }
    }
  }
  return dist
}

6. Deep Dive Strategy Lab: Shortest Path

Intuition Through Analogy

Think of this chapter like city route planning. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?