Dijkstra’s Algorithm: Finding Shortest Paths in Weighted Graphs

When you need to find the shortest path from one source vertex to all other vertices in a weighted graph, Dijkstra’s algorithm is the gold standard. It works on graphs with non-negative edge weights and delivers optimal paths with efficient time complexity. From GPS navigation to network routing, Dijkstra powers countless real-world systems that depend on finding optimal routes quickly.

The algorithm greedily selects the unvisited vertex with the smallest known distance, then explores its neighbors, updating distances if a shorter path is found. This simple but powerful strategy yields correctness because any path to a vertex must go through some intermediate vertex—and if we’re processing vertices in order of increasing distance, we’ll always discover the optimal path first.

Introduction

Dijkstra’s algorithm solves the single-source shortest path problem: given a weighted graph and a source vertex, find the minimum distance from the source to every other vertex. It achieves this with a greedy strategy—repeatedly select the unvisited vertex with the smallest known distance, then update distances to its neighbors. This deceptively simple approach delivers optimal paths in O((V + E) log V) time with a priority queue, making it one of the most important algorithms in computer science.

The elegance of Dijkstra lies in its correctness proof: any path to a vertex must go through some intermediate vertex, and if we process vertices in order of increasing distance from the source, we’ll always discover the optimal path to a vertex before we finalize its distance. This property holds only for non-negative edge weights—if negative edges existed, a shorter path could be found after a vertex was processed, invalidating the greedy choice. This constraint shapes where Dijkstra can be applied, but positive weights are common in real-world problems like road networks, routing tables, and game graph traversal.

Dijkstra appears everywhere in practice: GPS navigation systems find optimal routes, network protocols compute shortest paths for packet routing, game AI calculates movement costs, and dependency resolvers determine installation order. Understanding Dijkstra means understanding priority queue implementation trade-offs (binary heap vs Fibonacci heap), how to reconstruct shortest paths, and recognizing when its assumptions (non-negative weights) are violated. Variations like A* with heuristics build on Dijkstra’s foundation, making it essential knowledge for any graph algorithm work.

How Dijkstra’s Algorithm Works

The algorithm maintains a priority queue (min-heap) of vertices keyed by their current known distance from the source. Starting with the source at distance 0 and all others at infinity, we repeatedly extract the vertex with minimum distance and relax its outgoing edges.

import heapq
from collections import defaultdict

def dijkstra(graph, source):
    """
    Single-source shortest paths with Dijkstra's algorithm.

    Args:
        graph: Adjacency list dict[node -> [(neighbor, weight), ...]]
        source: Starting vertex

    Returns:
        dict mapping each vertex to its shortest distance from source
    """
    dist = {source: 0}
    pq = [(0, source)]  # (distance, vertex) min-heap
    visited = set()

    while pq:
        current_dist, u = heapq.heappop(pq)

        if u in visited:
            continue
        visited.add(u)

        # Skip if we've found a better path already
        if current_dist > dist.get(u, float('inf')):
            continue

        for v, weight in graph[u]:
            if v not in visited:
                new_dist = current_dist + weight
                if new_dist < dist.get(v, float('inf')):
                    dist[v] = new_dist
                    heapq.heappush(pq, (new_dist, v))

    return dist

Path Reconstruction

Knowing distances is useful, but often you need the actual path. Track predecessors during relaxation:

def dijkstra_with_path(graph, source, target):
    """Returns (distance, path_list) from source to target."""
    dist = {source: 0}
    pred = {source: None}
    pq = [(0, source)]
    visited = set()

    while pq:
        current_dist, u = heapq.heappop(pq)

        if u == target:
            # Reconstruct path
            path = []
            while u is not None:
                path.append(u)
                u = pred[u]
            return current_dist, path[::-1]

        if u in visited:
            continue
        visited.add(u)

        for v, weight in graph[u]:
            if v not in visited:
                new_dist = current_dist + weight
                if new_dist < dist.get(v, float('inf')):
                    dist[v] = new_dist
                    pred[v] = u
                    heapq.heappush(pq, (new_dist, v))

    return float('inf'), []  # Target unreachable

Dijkstra’s Algorithm Flow

graph TD
    A["Start: dist[source] = 0<br/>dist[others] = ∞"] --> B["Initialize priority queue<br/>with source at distance 0"]
    B --> C["Extract minimum distance<br/>unvisited vertex u"]
    C --> D{"Is u the target?"}
    D -->|Yes| E["Return distance<br/>and reconstruct path"]
    D -->|No| F[Mark u as visited]
    F --> G{"For each neighbor v of u not visited"}
    G -->|"new_dist < dist[v]"| H["Update dist[v] = new_dist<br/>pred[v] = u<br/>Push v to queue"]
    H --> G
    G -->|"new_dist >= dist[v]"| G
    G --> I{"Queue empty?"}
    I -->|Yes| J["Return all distances<br/>unreachable = ∞"]
    I -->|No| C
    E --> K[End]

When to Use Dijkstra’s Algorithm

Use Dijkstra when:

• You need single-source shortest paths
• All edge weights are non-negative
• You need efficient extraction of minimum distance vertices
• The graph is sparse (works better than dense matrix representations)

Don’t use Dijkstra when:

• Graph has negative edge weights (use Bellman-Ford instead)
• You need all-pairs shortest paths (consider Floyd-Warshall for small dense graphs)
• You need to detect negative cycles

Trade-off Analysis

Aspect	Dijkstra	Bellman-Ford	Floyd-Warshall
Time Complexity	O((V + E) log V)	O(V × E)	O(V³)
Space Complexity	O(V + E)	O(V)	O(V²)
Negative Weights	No	Yes	Yes
Single Source	Yes	Yes	Yes (all pairs)
Negative Cycle Detection	No	Yes	Yes

Production Failure Scenarios

1. Negative edge weights silently producing wrong results: Dijkstra’s assumes non-negative weights. If negative edges slip in, the algorithm may return incorrect shortest paths without any error indication. The greedy extraction guarantee breaks because a vertex extracted at distance X could later receive a shorter path through an unvisited negative edge. Always validate graph input to reject or handle negative weights before running Dijkstra.

2. Priority queue saturation under high edge counts: In dense graphs with E ≈ V², the min-heap can contain many entries per vertex as each relaxation pushes a new candidate. This causes heap operations to dominate runtime and memory. Monitor heap size growth and switch to the adjacency matrix variant when graph density exceeds ~50%.

3. Integer overflow with large distances: When edge weights are large or paths long, cumulative distance can overflow floating-point representation. Use a large constant (like 10**18) instead of float('inf') and check for overflow on each relaxation.

4. Graph with unreachable vertices: Always initialize distances properly and handle the case where target is unreachable. An infinite distance in the result means the vertex is not reachable from source.

Implementation Variants

# Using adjacency matrix (O(V²) - better for dense graphs)
def dijkstra_dense(graph, source):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    visited = [False] * n

    for _ in range(n):
        # Find minimum unvisited vertex
        u = -1
        min_dist = float('inf')
        for i in range(n):
            if not visited[i] and dist[i] < min_dist:
                min_dist = dist[i]
                u = i

        if u == -1:
            break
        visited[u] = True

        for v in range(n):
            if not visited[v] and graph[u][v] != float('inf'):
                new_dist = dist[u] + graph[u][v]
                if new_dist < dist[v]:
                    dist[v] = new_dist

    return dist

Quick Recap Checklist

• Use min-heap (priority queue) for efficient minimum extraction
• Initialize source distance to 0, all others to infinity
• Only process each vertex once (mark as visited)
• Relax edges from current vertex when distance is confirmed
• Reconstruct paths by tracking predecessors
• Don’t use with negative edge weights

Observability Checklist

Track Dijkstra’s algorithm runs to catch performance degradation and incorrect results.

Core Metrics

• Vertex extraction count (should be exactly V for complete runs)
• Edge relaxation count per vertex
• Priority queue size at each extraction
• Distance convergence per vertex
• Final distance values for all reachable vertices

Health Signals

• Extraction count exceeding V (potential loop or visited-set bug)
• Priority queue growing unbounded (heap saturation indicator)
• Distances not decreasing monotonically
• Same vertex extracted multiple times with different distances
• Runtime exceeding expected O((V + E) log V)

Alerting Thresholds

• Extraction count > V × 1.5: visited set implementation bug
• Priority queue size > 3V: graph density problem or relaxation bug
• Single vertex extracted > log V times: priority queue issue
• Runtime p99 > 100ms for V < 10K: investigate heap performance

Distributed Tracing

• Trace Dijkstra runs with vertex count, edge count, and heap operations
• Include source and target vertices in span attributes
• Correlate slow runs with high-density graphs or large V
• Track relaxation count as proxy for graph connectivity

Security Notes

Dijkstra’s algorithm has security implications when graph input is untrusted.

Graph poisoning with negative weights

If an attacker can control graph topology and injects negative-weight edges, Dijkstra’s will silently produce incorrect shortest paths. The algorithm assumes non-negative weights and the greedy extraction guarantee breaks with negative edges. No error is raised—the results are simply wrong.

Fix: Validate all edge weights before running Dijkstra. Reject graphs containing any negative weights, or use Bellman-Ford which handles negative weights correctly. Log when negative weights are encountered.

Priority queue exhaustion via crafted dense graphs

An attacker who controls graph input can craft a dense graph causing heap operations to dominate runtime. With E ≈ V², each of V vertex extractions must scan E edges, causing O(V³) behavior instead of O((V + E) log V).

Fix: Set maximum limits on vertex and edge counts. Detect graph density at input time and switch to the O(V²) adjacency matrix variant for dense graphs. Set time budgets per extraction and abort if exceeded.

Path traversal attacks via specially crafted shortest paths

If Dijkstra output drives downstream path traversal (routing, navigation), an attacker who crafts the graph topology can direct traversal through specific nodes for reconnaissance or exploitation.

Fix: Validate that computed paths conform to expected topology constraints. Do not blindly trust shortest-path output without verifying the path makes sense in your application context.

Interview Questions

Further Reading

Dive deeper into Dijkstra’s algorithm and related topics with these resources:

Books

• “Introduction to Algorithms” (CLRS) — Chapter 24 covers single-source shortest paths with rigorous proofs of Dijkstra’s correctness.
• “Algorithms” by Robert Sedgewick & Kevin Wayne — Practical implementations and applications of Dijkstra’s algorithm in graph theory.

Academic Papers

• Edsger W. Dijkstra (1959) — “A Note on Two Problems in Connexion with Graphs” — The original paper describing the algorithm.
• Michael L. Fredman & Robert E. Tarjan (1987) — “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms” — Introduces the Fibonacci heap variant achieving O(V log V + E).

Online Resources

• Visualgo.net - Dijkstra’s Algorithm Visualization — Interactive step-by-step visualization.
• USACO Guide - Dijkstra’s Algorithm — Competitive programming focused treatment.
• CP-Algorithms - Dijkstra’s Algorithm — Detailed explanation with multiple language implementations.

Related Algorithms

• Bellman-Ford Algorithm — Handles negative edge weights and detects negative cycles at O(V × E) cost.
• Floyd-Warshall Algorithm — All-pairs shortest paths in O(V³) for dense graphs.
• A* Search — Extension of Dijkstra’s with heuristics for goal-directed pathfinding.
• Bidirectional Dijkstra — Runs two simultaneous searches from source and target for faster convergence.

Conclusion

Dijkstra’s algorithm finds single-source shortest paths by greedily selecting the unvisited vertex with minimum distance and relaxing its edges. It runs in O((V + E) log V) with a binary min-heap and requires non-negative edge weights—use Bellman-Ford or Floyd-Warshall when negative weights are present. For dense graphs, the adjacency matrix variant runs in O(V²). Path reconstruction requires tracking predecessor pointers during relaxation.