Quartz 4

Dijkstra's Algorithm - Implementation Patterns

5 min read

Dijkstra’s Algorithm - Implementation Patterns

Priority Queue Choice Matters

The priority queue implementation fundamentally determines Dijkstra’s performance:

ImplementationExtract-MinDecrease-KeyTotal Complexity
Binary HeapO(log V)O(log V)O((V + E) log V)
Fibonacci HeapO(log V)O(1) amortizedO(E + V log V)
Array (linear search)O(V)O(1)O(V²)

Practical insight: Binary heap is usually best unless E ≈ V² (dense graphs), where array-based is simpler and competitive.

The Visited Set Pattern

A common implementation mistake is processing nodes multiple times:

# WRONG: No visited check
while pq:
    dist, node = heappop(pq)
    for neighbor, weight in graph[node].items():
        new_dist = dist + weight
        if new_dist < distances[neighbor]:
            distances[neighbor] = new_dist
            heappush(pq, (new_dist, neighbor))

This creates duplicate entries in the priority queue, degrading from O((V+E) log V) to O((V+E) log E).

# CORRECT: Check if visited
while pq:
    dist, node = heappop(pq)
    if node in visited:  # Skip duplicates
        continue
    visited.add(node)
    
    for neighbor, weight in graph[node].items():
        new_dist = dist + weight
        if new_dist < distances[neighbor]:
            distances[neighbor] = new_dist
            heappush(pq, (new_dist, neighbor))

Lazy vs Eager Updates

Lazy (Python heapq default)

# Just push new entries, filter at extraction
if new_dist < distances[neighbor]:
    distances[neighbor] = new_dist
    heappush(pq, (new_dist, neighbor))  # Create duplicate

Pros: Simpler, works with heapq Cons: More memory, more log operations

Eager (requires decrease-key)

# Update existing entry in place
if new_dist < distances[neighbor]:
    distances[neighbor] = new_dist
    pq.decrease_key(neighbor, new_dist)  # Needs custom heap

Pros: Fewer operations, theoretically optimal Cons: Complex implementation, rarely worth it in practice

Path Reconstruction Pattern

Track predecessors during relaxation:

def dijkstra_with_path(graph, start, target):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    predecessors = {node: None for node in graph}
    pq = [(0, start)]
    visited = set()
    
    while pq:
        dist, current = heappop(pq)
        
        if current == target:  # Early termination
            break
            
        if current in visited:
            continue
        visited.add(current)
        
        for neighbor, weight in graph[current].items():
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                predecessors[neighbor] = current
                heappush(pq, (new_dist, neighbor))
    
    # Reconstruct path
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = predecessors[current]
    path.reverse()
    
    return distances[target], path

Early Termination for Single Target

If you only need the path to one target, stop when you extract it:

while pq:
    dist, current = heappop(pq)
    
    if current == target:
        return dist  # Found it!
    
    # ... rest of algorithm

This is correct because Dijkstra’s Algorithm - The Greedy Invariant guarantees the first extraction has the optimal distance.

Graph Representation Choice

Adjacency List (dict of dict)

graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'C': 1, 'D': 5},
    'C': {'D': 8},
}

Best for: Sparse graphs (E << V²)

Adjacency Matrix (2D array)

# INF represents no edge
graph = [
    [0,   4,   2,   INF],
    [INF, 0,   1,   5  ],
    [INF, INF, 0,   8  ],
]

Best for: Dense graphs (E ≈ V²)

For Dijkstra, adjacency list is typically better since we iterate over neighbors frequently.

Handling Disconnected Graphs

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    # ... run algorithm ...
    
    # Check for unreachable nodes
    unreachable = [node for node, dist in distances.items() 
                   if dist == float('inf')]
    
    return distances, unreachable

Bidirectional Dijkstra Optimization

For single source-target queries, run Dijkstra from both ends:

def bidirectional_dijkstra(graph, start, target):
    # Forward search from start
    forward = dijkstra_partial(graph, start)
    # Backward search from target (needs reverse graph)
    backward = dijkstra_partial(reverse_graph, target)
    
    # Find meeting point with minimum total distance
    meeting = min(graph.nodes, 
                  key=lambda n: forward[n] + backward[n])
    
    return forward[meeting] + backward[meeting]

This can cut search space roughly in half for large graphs.

When Dijkstra is the Right Choice

Use Dijkstra when:

  1. Single-source shortest paths needed
  2. Non-negative weights (or you’ll need Bellman-Ford Algorithm - Negative Weight Handling)
  3. Finding paths to multiple targets from one source
  4. Dense graphs where E = Ω(V²) and simple array-based PQ works

Don’t use Dijkstra when:

  1. Unweighted graphs → Use BFS (simpler and faster)
  2. Negative weights → Use Bellman-Ford Algorithm - Edge Relaxation Pattern
  3. All-pairs shortest paths → Consider Floyd-Warshall Algorithm
  4. A heuristic available* → Use A* (Dijkstra with guidance)

Common Implementation Bugs

  1. Forgetting visited check → O((V+E) log E) instead of O((V+E) log V)
  2. Using wrong tuple order → (node, dist) instead of (dist, node) breaks heapq
  3. Not initializing all nodes → Missing nodes get no distance estimate
  4. Comparing to visited before processing → Can prevent finding paths

The Testing Pattern

def test_dijkstra():
    # Triangle inequality test
    graph = {'A': {'B': 4, 'C': 2}, 'B': {'C': 1}, 'C': {}}
    distances = dijkstra(graph, 'A')
    assert distances['B'] <= distances['A'] + 4
    assert distances['C'] <= distances['A'] + 2
    assert distances['C'] <= distances['B'] + 1
    
    # Shortest path optimality
    assert distances['C'] == 2  # Direct is better than A→B→C

Reconstruction: The visited set optimization prevents duplicate processing. Binary heap is typically best due to good constant factors despite Fibonacci heap’s better asymptotic complexity.

Graph View

Backlinks