Dijkstra's Algorithm: Shortest Paths Explained

Dijkstra’s algorithm computes the shortest path from a single source to every other node in a weighted graph, as long as edge weights are non-negative. It is the standard tool for routing, map navigation, network protocols, and any problem framed as least-cost traversal.

The Core Idea

Dijkstra maintains a tentative distance from the source to every node. Initially the source has distance zero and every other node has infinity. We repeatedly pick the unvisited node with the smallest tentative distance, mark it as finalized, and relax its outgoing edges. Relaxing an edge u to v with weight w means checking whether dist[u] + w improves dist[v], and updating if so.

The greedy choice works because edge weights are non-negative. Once we pop a node from the priority queue with its smallest tentative distance, no future path can be shorter, since any detour would only add non-negative weight.

Why Non-Negative Weights Matter

If the graph contains a negative edge, the greedy invariant breaks. A node we considered finalized could later be reached via a cheaper path that dips through a negative edge. For graphs with negative weights, use Bellman-Ford instead.

Python Implementation

Here is a clean implementation using a binary heap. The graph is represented as an adjacency list mapping each node to a list of neighbor and weight pairs.

import heapq
from math import inf

def dijkstra(graph, source):
    dist = {node: inf for node in graph}
    dist[source] = 0
    visited = set()
    pq = [(0, source)]

    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if v in visited:
                continue
            new_dist = d + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
    return dist

graph = {
    'A': [('B', 4), ('C', 1)],
    'B': [('D', 1)],
    'C': [('B', 2), ('D', 5)],
    'D': []
}
print(dijkstra(graph, 'A'))

The output gives the shortest distance from A to every other node. Note the use of a lazy deletion pattern: we may push duplicate entries to the heap, but we skip them when they pop out as already visited.

Reconstructing the Path

To recover the actual path, store a parent map alongside distances. When you relax an edge and update dist[v], set parent[v] = u. To get the path to a target, walk parents back to the source and reverse the list.

def dijkstra_with_path(graph, source, target):
    dist = {node: inf for node in graph}
    parent = {node: None for node in graph}
    dist[source] = 0
    pq = [(0, source)]

    while pq:
        d, u = heapq.heappop(pq)
        if u == target:
            break
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))

    path = []
    node = target
    while node is not None:
        path.append(node)
        node = parent[node]
    return dist[target], path[::-1]

This version also includes an early exit once the target is finalized, which can save substantial work on large graphs.

Complexity Analysis

With a binary heap and adjacency list, Dijkstra runs in O((V + E) log V) time, where V is the number of vertices and E the number of edges. Each edge can be relaxed once, and each push or pop costs log V. Space is O(V) for the distance map plus the heap.

For dense graphs where E approaches V squared, a simple array-based implementation that scans all nodes for the minimum each iteration runs in O(V squared), and that can actually be faster than the heap version in practice. For sparse graphs, the heap version dominates.

A Fibonacci heap gives a theoretical O(E + V log V) bound, but the constant factors are large enough that binary heaps win for nearly all practical inputs.

Common Pitfalls

Forgetting the visited check after popping is the most common bug. Without it, the algorithm still produces correct distances but wastes time reprocessing nodes.

Another trap is treating Dijkstra as a generic shortest path tool. It is not. If your graph has negative edges, you need Bellman-Ford. If all edges have unit weight, BFS is simpler and faster. If you need shortest paths between every pair of nodes, Floyd-Warshall may be more appropriate.

Be careful with floating-point edge weights. Accumulated rounding errors can cause inconsistent comparisons. When precision matters, scale weights to integers if possible.

Bidirectional and A-Star Variants

For point-to-point queries on huge graphs, plain Dijkstra explores too much of the graph. Two common optimizations are bidirectional Dijkstra, which runs searches from both source and target until they meet, and A-star, which adds a heuristic estimate of remaining distance to guide exploration. Both preserve correctness while pruning the search space dramatically.

When to Use It

Reach for Dijkstra whenever you need shortest paths in a weighted graph with non-negative weights. Typical applications include road networks, network routing tables, dependency resolution with costs, and game pathfinding on weighted grids. Many problem statements that mention “minimum cost to reach” can be reframed as Dijkstra on an implicit graph.

If you find yourself comparing it to other graph traversals, revisit the overview in /blog/graphs-bfs-and-dfs for unweighted exploration, or /blog/sorting-algorithms-overview to see how priority queues underpin both sorting and shortest-path work.

Wrap up

Dijkstra is a greedy algorithm that finalizes nodes in order of distance from the source. The heap-based version runs in O((V + E) log V) and is the default tool for non-negative weighted shortest paths. Once you can implement it from memory, variations like A-star and bidirectional search become natural extensions.