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

September 7, 2025·7 min read

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.

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:

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 and add the source node with distance 0.
Visit the closest node: Extract the node with the smallest distance from the priority queue.
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.
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', 1), ('C', 4)],
    'B': [('C', -3)],       # Negative edge!
    'C': []
}

# Dijkstra finds: A -> C with distance 4
# Actual shortest: A -> B -> C with distance 1 + (-3) = -2

For graphs with negative weights (but no negative cycles), use the Bellman-Ford algorithm 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: 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.