🛣️ Dijkstra's Algorithm Fundamentals

🎯 What is Dijkstra's Algorithm?

Dijkstra's Algorithm is a greedy shortest-path algorithm invented by Edsger W. Dijkstra in 1956. It finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It's the foundation of countless GPS navigation systems and network routing protocols.

Time: O((V+E) log V) with PQ | Space: O(V) | Non-negative weights only

Deep Explanation

Core Insight: Dijkstra's algorithm maintains a set of vertices whose shortest distance from the source is known. At each step, it selects the vertex with the smallest tentative distance, relaxes its outgoing edges, and adds it to the settled set. This greedy choice works because all edge weights are non-negative.

Key Intuition: If the shortest path from A to B goes through C, then the A→C subpath must also be optimal (optimal substructure). Dijkstra exploits this with a priority queue.

📌 Greedy Algorithm📌 Single Source Shortest Path📌 Non-negative Weights📌 Relaxation Principle
import heapq def dijkstra(graph, start): # graph: adjacency list {node: [(neighbor, weight), ...]} distances = {node: float('inf') for node in graph} distances[start] = 0 pq = [(0, start)] # (distance, node) while pq: current_dist, current = heapq.heappop(pq) if current_dist > distances[current]: continue # outdated entry for neighbor, weight in graph[current]: distance = current_dist + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(pq, (distance, neighbor)) return distances graph = { 'A': [('B', 4), ('C', 2)], 'B': [('C', 1), ('D', 5)], 'C': [('D', 8), ('E', 10)], 'D': [('E', 2)], 'E': [] } print(dijkstra(graph, 'A')) # {'A':0, 'B':4, 'C':2, 'D':9, 'E':11}

📐 Algorithm Walkthrough

🎯 Step-by-Step Execution

  • Step 0: Initialize distances: dist[source]=0, all others = ∞. PQ = [(0, source)]
  • Step 1: Pop (0, A). Relax edges A→B(4): dist[B]=4, A→C(2): dist[C]=2. PQ now has (2,C), (4,B).
  • Step 2: Pop (2, C). Relax C→D(8): dist[D]=10 (∞→10). C→E(10): dist[E]=10. PQ: (4,B), (10,D), (10,E).
  • Step 3: Pop (4, B). Relax B→C(1): 4+1=5 > dist[C]=2 → ignore. B→D(5): 4+5=9 < 10 → update dist[D]=9, push (9,D).
  • Step 4: Pop (9, D). Relax D→E(2): 9+2=11 > dist[E]=10 → ignore.
  • Result: distances = {A:0, B:4, C:2, D:9, E:10}.

⏱️ Time & Space Complexity

🎯 Complexity Analysis

  • Naive Array Implementation: O(V²) — good for dense graphs
  • Binary Heap + Adjacency List: O((V+E) log V) — best for sparse graphs
  • Fibonacci Heap: O(E + V log V) — theoretical optimum
  • Space Complexity: O(V) for distances and priority queue

Why O((V+E) log V)?

Each vertex is extracted once (V pops O(log V) each). Each edge triggers at most one decrease-key/push operation (E times O(log V) each). Total = (V+E) log V.

⛲ Priority Queue vs Array Implementation

🎯 Trade-offs

  • Array (O(V²)): Simple, faster for dense graphs where E ≈ V²
  • Binary Heap (O((V+E)log V)): Better for sparse graphs (E = O(V))
  • Fibonacci Heap (O(E + V log V)): Theoretical, high constant overhead
def dijkstra_array(graph, start): V = len(graph) dist = [float('inf')] * V visited = [False] * V dist[start] = 0 for _ in range(V): u = min((dist[i], i) for i in range(V) if not visited[i])[1] visited[u] = True for v, w in graph[u]: if not visited[v] and dist[u] + w < dist[v]: dist[v] = dist[u] + w return dist

💻 Multiple Implementations

# 1. With path reconstruction def dijkstra_with_path(graph, start, end): distances = {node: float('inf') for node in graph} distances[start] = 0 previous = {node: None for node in graph} pq = [(0, start)] while pq: dist, curr = heapq.heappop(pq) if dist > distances[curr]: continue if curr == end: break for nbr, w in graph[curr]: new_dist = dist + w if new_dist < distances[nbr]: distances[nbr] = new_dist previous[nbr] = curr heapq.heappush(pq, (new_dist, nbr)) # reconstruct path path, node = [], end while node is not None: path.append(node) node = previous[node] return path[::-1], distances[end] # 2. Using defaultdict for cleaner code from collections import defaultdict def dijkstra_defaultdict(edges, start): graph = defaultdict(list) for u, v, w in edges: graph[u].append((v, w)) # same PQ logic as above

⚠️ Negative Weights & Limitations

🎯 Why Dijkstra Fails with Negative Edges

Dijkstra's algorithm assumes that once a node's distance is finalized (extracted from PQ), it's optimal. With negative edges, a later discovered path could be shorter. Use Bellman-Ford for graphs with negative weights (detects negative cycles).

Counterexample

Graph: A→B (1), A→C (4), B→C (-3). Dijkstra from A finalizes B first (dist=1), then C via B is 1-3=-2, but Dijkstra would already have set C=4 incorrectly.

📊 Step-by-Step Visualization

🎯 Graph: 4 nodes

Nodes: 0 (source), 1, 2, 3.
Edges: 0→1 (4), 0→2 (1), 2→1 (2), 2→3 (5), 1→3 (1).
Process: Start 0: relax to 1(4) & 2(1). Pick 2. Relax 2→1 (1+2=3 < 4) update 1 to 3. Relax 2→3 (1+5=6). Pick 1 (dist=3). Relax 1→3 (3+1=4 < 6) update 3 to 4. Final: 0:0, 2:1, 1:3, 3:4.

✅ Correctness Proof & Invariants

🎯 Invariant: When a node is extracted from PQ, its distance is optimal

Proof by induction: Base case source is optimal. Assume all extracted nodes are optimal. For the next node u with min distance, any alternative path must go through some unsettled node v with distance ≥ dist[u] (since all edge weights ≥ 0), so cannot be shorter. Therefore u's distance is final.

📈 Comparison with Other SP Algorithms

  • vs Bellman-Ford: Bellman-Ford handles negative weights, O(VE). Dijkstra is faster but requires non-negative weights.
  • vs Floyd-Warshall: All-pairs shortest paths, O(V³). Dijkstra run V times gives O(V(E+V)log V) ≈ faster for sparse graphs.
  • vs A*: A* uses heuristics for goal-directed search (Dijkstra is A* with heuristic=0).
  • vs BFS: BFS for unweighted graphs is O(V+E) – special case of Dijkstra with uniform weight 1.

⚡ Optimizations & Variants

  • Dial's Algorithm: For integer weights and small max weight, O(V+E+W) using bucket queues.
  • Radix Heap: Faster than binary heap for integer weights.
  • Delta-Stepping: Parallel-friendly Dijkstra variant.
  • Lazy Deletion: Skip outdated PQ entries instead of decrease-key (used in example).

🔄 Bidirectional Dijkstra

🎯 Two-Sided Search for Speed

Run Dijkstra simultaneously from source and target. Stop when the two search frontiers meet. In practice, this explores ~2x fewer nodes on road networks, offering massive speedups.

def bidirectional_dijkstra(graph, source, target): dist_f = {source: 0} dist_b = {target: 0} pq_f = [(0, source)] pq_b = [(0, target)] visited_f, visited_b = set(), set() best = float('inf') while pq_f and pq_b: # alternate expansions # stop when dist_f + dist_b >= best return best

🚀 Parallel & GPU Dijkstra

🎯 Concurrent Shortest Paths

Multi-source Dijkstra (multiple start nodes) is naturally parallelizable. GPU implementations use warp-level primitives and bucketed queues for massive speedups on graphs up to millions of nodes.

🌍 Real-World Applications

  • GPS & Google Maps: Road network navigation (with heuristics → A*).
  • Network Routing (OSPF): Open Shortest Path First protocol uses Dijkstra.
  • Social Networks: Degrees of separation (unweighted BFS).
  • Game Development: Pathfinding in static environments.
  • Telecommunications: Optimal data packet routing.

💪 Practice & Problem Patterns

🎯 Classic Dijkstra Problems

  • Network Delay Time (LeetCode 743): Max distance from source to all nodes.
  • Cheapest Flights Within K Stops: Dijkstra with hop constraint (Bellman-Ford variant).
  • Path With Minimum Effort: Min-max path uses Dijkstra with different relaxation.
  • Shortest Path in Grid with Obstacles: 0-1 BFS = Dijkstra on binary weights.
  • Swim in Rising Water: Dijkstra on maximum weight path.
# LeetCode 743 - Network Delay Time def networkDelayTime(times, n, k): graph = [[] for _ in range(n+1)] for u,v,w in times: graph[u].append((v,w)) dist = [float('inf')]*(n+1) dist[k] = 0 pq = [(0,k)] while pq: d, node = heapq.heappop(pq) if d > dist[node]: continue for nei, w in graph[node]: nd = d + w if nd < dist[nei]: dist[nei] = nd heapq.heappush(pq, (nd, nei)) max_dist = max(dist[1:]) return max_dist if max_dist != float('inf') else -1