Dijkstra’s Algorithm - The Greedy Invariant

Core Insight

Dijkstra’s algorithm works because of a powerful invariant: once a node is marked as visited (extracted from the priority queue), we have definitively found the shortest path to it.

This greedy property only holds under one critical constraint: all edge weights must be non-negative.

Why Greedy Works Here

The algorithm always selects the unvisited node with the smallest known distance. This greedy choice is optimal because:

1. No future discovery can improve it: Since all weights are non-negative, any path through an unvisited node would add only positive weight, making it longer
2. Optimal substructure: The shortest path to a node consists of the shortest path to some intermediate node plus one edge
3. Monotonicity: Distances never decrease as we explore farther from the source

The Mathematical Guarantee

At each step, let d[v] be our current distance estimate to node v.

For the node u we’re about to visit:

• d[u] is minimal among all unvisited nodes
• Any path to u through an unvisited node w would have length ≥ d[w] + weight(w,u)
• Since d[w] ≥ d[u] and weight(w,u) ≥ 0, we have d[w] + weight(w,u) ≥ d[u]

Therefore, d[u] is optimal.

When the Invariant Breaks

With negative weights, this guarantee fails:

Source (A) --(-5)--> B --(1)--> C
         \                      /
          \--------(3)----------/

Using Dijkstra:

1. Visit A (distance 0)
2. Visit C (distance 3) - marked as final!
3. Visit B (distance -5)
4. Would update C to distance -4, but C is already marked as visited

The greedy choice failed because we assumed we couldn’t find a shorter path later.

Implementation Pattern

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    visited = set()
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        # THE INVARIANT: Once visited, distance is optimal
        if current in visited:
            continue
        visited.add(current)  # Mark as finalized
        
        # Explore neighbors
        for neighbor, weight in graph[current].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

Comparison with Other Approaches

• BFS as Wavefront Propagation: Works greedily with uniform weights (weight = 1)
• Bellman-Ford Algorithm - Edge Relaxation: Doesn’t assume greedy is optimal, iterates all edges
• Union Find: Different problem (connectivity, not shortest paths)

Key Takeaway

Dijkstra’s greedy approach is a special case that exploits the structure of non-negative weighted graphs. It’s faster than Bellman-Ford Algorithm - Edge Relaxation precisely because it can make this greedy guarantee.

---

Reconstruction: The invariant follows from the proof by contradiction above. Non-negative weights ensure monotonicity of distance estimates.