# The Hidden Algorithm That Runs Your Life: Dijkstra's Algorithm Explained

> Learn how Dijkstra's shortest-path algorithm works, powers Google Maps and internet routing, and where it breaks down, with a Python implementation.

- Author: Shawn Ng (https://shawnng.com/about)
- Published: 2025-09-07
- Updated: 2026-09-30
- Canonical URL: https://shawnng.com/posts/dijkstras-algorithm-explained
- Topics: algorithms, dijkstra, graph-theory, software-engineering

## Key takeaways

- Dijkstra's algorithm guarantees the optimal shortest path in any graph whose edge weights are all non-negative.
- The binary heap implementation runs in O((V + E) log V), which is fast enough for most practical applications.
- Once a node is dequeued from the priority queue its shortest distance is final, which is why negative edges break the algorithm.
- For graphs with negative weights but no negative cycles, use the Bellman-Ford algorithm instead, which runs in O(V * E) time.
- At continent scale, production systems add A* search, contraction hierarchies, or bidirectional search on top of Dijkstra.

Every time you ask Google Maps for directions, every time a data packet finds its way across the internet to your device, and every time a video game NPC navigates around obstacles, the same algorithm is quietly doing the work. It is called Dijkstra's algorithm, and it solves one of the most fundamental problems in computer science: finding the shortest path between two points in a graph.

Check out the full video on my YouTube channel [Divide and Quantum](https://www.youtube.com/watch?v=CBas9UaDxqI).

## The Problem: Shortest Path in a Weighted Graph

A graph is a collection of nodes (vertices) connected by edges. When edges have weights representing distance, cost, or time, finding the path with the minimum total weight between two nodes is the **shortest-path problem**.

This is deceptively hard. You cannot just pick the nearest neighbor at each step because a greedy choice might lead you into a dead end or a longer overall path. You need an algorithm that systematically explores possibilities and guarantees the optimal answer.

## How Dijkstra's Algorithm Works

Edsger Dijkstra proposed his algorithm in 1956 and published it in 1959. The core idea is elegant: explore the graph outward from the source node, always expanding the closest unvisited node first.

Here is the step-by-step process:

1. **Initialize**: Set the distance to the source node as 0 and all other nodes as infinity. Mark all nodes as unvisited. Create a [priority queue](https://shawnng.com/posts/data-structures-every-developer-should-master) and add the source node with distance 0.
2. **Visit the closest node**: Extract the node with the smallest distance from the priority queue.
3. **Relax neighbors**: For each unvisited neighbor of the current node, calculate the distance through the current node. If this distance is smaller than the neighbor's current recorded distance, update it.
4. **Repeat**: Continue until you have visited the destination node or the priority queue is empty.

The algorithm works because once a node is visited (dequeued from the priority queue), we are guaranteed to have found the shortest path to it. This guarantee relies on one critical assumption: **all edge weights must be non-negative**.

## Python Implementation

Let us build Dijkstra's algorithm from scratch using Python's `heapq` module for the priority queue:

```python
import heapq

def dijkstra(graph, start):
    """
    Find shortest paths from start to all reachable nodes.

    Args:
        graph: dict of {node: [(neighbor, weight), ...]}
        start: the source node

    Returns:
        distances: dict of shortest distance to each node
        predecessors: dict to reconstruct the shortest path
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    predecessors = {node: None for node in graph}
    priority_queue = [(0, start)]
    visited = set()

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)

        # Skip if we already found a shorter path
        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph[current_node]:
            if neighbor in visited:
                continue

            new_dist = current_dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                predecessors[neighbor] = current_node
                heapq.heappush(priority_queue, (new_dist, neighbor))

    return distances, predecessors


def reconstruct_path(predecessors, start, end):
    """Walk backwards through predecessors to build the path."""
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = predecessors[current]
    path.reverse()

    if path[0] != start:
        return []  # No path exists
    return path
```

### Running It

```python
graph = {
    'A': [('B', 4), ('C', 1)],
    'B': [('D', 1)],
    'C': [('B', 2), ('D', 5)],
    'D': [('E', 3)],
    'E': []
}

distances, predecessors = dijkstra(graph, 'A')

print("Shortest distances from A:")
for node, dist in sorted(distances.items()):
    print(f"  A -> {node}: {dist}")

# A -> A: 0
# A -> B: 3  (A -> C -> B)
# A -> C: 1  (A -> C)
# A -> D: 4  (A -> C -> B -> D)
# A -> E: 7  (A -> C -> B -> D -> E)

path = reconstruct_path(predecessors, 'A', 'E')
print(f"\nShortest path A -> E: {' -> '.join(path)}")
# Shortest path A -> E: A -> C -> B -> D -> E
```

Notice that the shortest path from A to B is not the direct edge (weight 4) but the route through C (weight 1 + 2 = 3). This is exactly the kind of non-obvious solution that Dijkstra's algorithm finds.

## Time Complexity

The performance depends on your priority queue implementation:

| Implementation | Time Complexity |
|---|---|
| Array (naive) | O(V^2) |
| Binary heap (heapq) | O((V + E) log V) |
| Fibonacci heap | O(V log V + E) |

For sparse graphs where E is close to V, the binary heap version is efficient. For dense graphs where E is close to V^2, the naive array version can actually be faster because it avoids the overhead of heap operations. In practice, the binary heap version (what we implemented above) is the best general-purpose choice.

## Real-World Applications

### Google Maps and Navigation

Road networks are naturally modeled as weighted graphs. Intersections are nodes, roads are edges, and travel time is the weight. Dijkstra's algorithm (and its variants) finds the fastest route. In practice, Google uses optimized versions like A* and contraction hierarchies that precompute shortcuts for faster queries, but Dijkstra is the foundation.

### Internet Routing (OSPF)

The Open Shortest Path First (OSPF) protocol, used by routers across the internet, runs Dijkstra's algorithm. Each router builds a map of the network topology and computes the shortest path to every other router. When you load a webpage, your data packets follow these computed paths.

### Social Network Feeds

Finding the shortest connection between two people on LinkedIn ("2nd degree connection") is a shortest-path problem. Recommendation engines use graph distances to suggest friends or content.

### Game AI and Pathfinding

When an NPC in a video game navigates around walls and obstacles, it is typically running A* (a Dijkstra variant with a heuristic) on a grid or navigation mesh. The algorithm finds a path that avoids obstacles while minimizing travel distance.

### Airline Route Optimization

Airlines model their route networks as graphs with costs including fuel, crew time, and gate fees. Dijkstra-based algorithms help compute optimal itineraries for passengers and cargo.

## Where Dijkstra's Algorithm Breaks Down

Dijkstra's algorithm is powerful, but it has clear limitations.

### Negative Edge Weights

This is the most important limitation. Dijkstra's algorithm assumes that once a node is visited, its shortest distance is finalized. Negative edges violate this assumption because a longer path might later become shorter by traversing a negative edge.

```python
# This graph breaks Dijkstra's algorithm
broken_graph = {
    'A': [('B', 2), ('C', 3)],
    'B': [],
    'C': [('B', -2)],       # Negative edge!
}

distances, _ = dijkstra(broken_graph, 'A')
print(distances['B'])
# 2: B is popped at distance 2 and finalized before C is explored,
# so the edge C -> B is skipped.
# Actual shortest: A -> C -> B with distance 3 + (-2) = 1
```

The negative edge has to point back into a node that is already finalized. If it points forward, as in A -> B -> C with B -> C negative, the relaxation still happens in time and Dijkstra gets lucky.

For graphs with negative weights (but no negative cycles), use the **[Bellman-Ford algorithm](https://shawnng.com/posts/bellman-ford-arbitrage)** instead, which runs in O(V * E) time.

### Negative Cycles

If a graph contains a cycle where the total weight is negative, the concept of "shortest path" becomes meaningless. You could loop around the cycle forever, reducing the distance infinitely. Neither Dijkstra nor Bellman-Ford produces a meaningful shortest path here, though Bellman-Ford can at least detect that a negative cycle exists.

### Very Large Graphs

For continent-scale road networks with millions of nodes, running Dijkstra from scratch for every query is too slow. Production systems use preprocessing techniques like:

- **[A\* search](https://shawnng.com/posts/astar-pathfinding-vs-dijkstra)**: Uses a heuristic (like straight-line distance) to guide the search toward the destination, dramatically reducing the number of nodes explored.
- **Contraction hierarchies**: Precomputes shortcut edges that allow queries to skip over unimportant nodes.
- **Bidirectional search**: Runs Dijkstra simultaneously from the source and destination, meeting in the middle.

### Dynamic Graphs

Dijkstra computes shortest paths for a static snapshot of the graph. If edge weights change frequently (like real-time traffic), the algorithm must be re-run. Incremental variants exist but add significant complexity.

## Key Takeaways

Dijkstra's algorithm is one of those foundational pieces of computer science that quietly powers the modern world. It guarantees the optimal shortest path in any graph with non-negative edge weights. The binary heap implementation runs in O((V + E) log V) time, which is fast enough for most practical applications. When it falls short due to negative weights, massive scale, or dynamic conditions, specialized variants and preprocessing techniques fill the gaps.

Understanding Dijkstra's algorithm is not just an academic exercise. It gives you a framework for thinking about optimization problems, network design, and the graph structures that underlie so many systems you interact with every day.

## Frequently asked questions

### What is the time complexity of Dijkstra's algorithm?

With a binary heap it is O((V + E) log V). A naive array implementation is O(V^2), which can be faster on dense graphs, and a Fibonacci heap gives O(V log V + E).

### Why does Dijkstra's algorithm fail with negative edge weights?

Because it assumes a node's distance is final the moment that node is visited. A negative edge can make a longer path become shorter later, which violates the assumption. Use Bellman-Ford when weights can be negative.

### What is the difference between Dijkstra and A*?

A* is a Dijkstra variant that adds a heuristic, such as straight-line distance, to guide the search toward the destination and dramatically reduce the number of nodes explored. Plain Dijkstra expands outward from the source with no sense of where the goal is.

### Where is Dijkstra's algorithm used in real life?

It underpins map navigation, the OSPF internet routing protocol, shortest-connection queries on social networks, game pathfinding, and airline route optimization. Google Maps uses optimized variants such as A* and contraction hierarchies, but Dijkstra is the foundation.

## Sources

- E. W. Dijkstra (1959). [A note on two problems in connexion with graphs](https://doi.org/10.1007/BF01386390). Numerische Mathematik.
- Philip L. Frana, Thomas J. Misa (2010). [An interview with Edsger W. Dijkstra](https://doi.org/10.1145/1787234.1787249). Communications of the ACM.
- Michael L. Fredman, Robert Endre Tarjan (1987). [Fibonacci heaps and their uses in improved network optimization algorithms](https://doi.org/10.1145/28869.28874). Journal of the ACM.
- J. Moy (1998). [OSPF Version 2](https://www.rfc-editor.org/rfc/rfc2328). IETF (RFC 2328).
- Richard Bellman (1958). [On a routing problem](https://doi.org/10.1090/qam/102435). Quarterly of Applied Mathematics.
- Robert Geisberger, Peter Sanders, Dominik Schultes, Daniel Delling (2008). [Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks](https://doi.org/10.1007/978-3-540-68552-4_24). Experimental Algorithms (WEA 2008), Lecture Notes in Computer Science, Springer.