Dijkstra's algorithm

You’ll recognise it when

• You want the cheapest or fastest route, and edges have different costs: travel times, prices, delays.
• There is one starting point, and you need the distance to one node or to all of them.
• Every weight is zero or more.
• The “cost” of a path only grows as the path gets longer, such as a sum of weights or the largest step so far.

If every edge costs the same, plain BFS is simpler and faster. If some edges are negative, you need Bellman-Ford instead.

The idea

Pour water into a network of pipes at the source. The water reaches the nearest junction first, then the next nearest, and so on. When the water arrives at a junction, nothing can beat it there later: every other route is still on its way and already longer.

Dijkstra does the same with a min-heap. It keeps a best-known distance dist for every node and always takes the node with the smallest one. That node is settled: its distance is final. Then it checks each edge out of it, and if going through it is a shortcut to a neighbour, it lowers that neighbour’s dist.

How it works

The graphic runs the algorithm on a small directed graph from node 0. Scroll through the steps and the graphic follows along. You can also press play, or edit the edges and try your own graph.

Why it’s correct: when the heap gives you the smallest d still waiting, every other unsettled node is at least d away. Any other route to u must pass through one of them, and since edges never have negative weight, that route can only get longer from there. So d can’t be beaten, and u is safe to settle.

import heapq


def dijkstra(graph, source):
    """Shortest distance from source to every node, or -1 if unreachable.
    graph[u] is a list of (v, w) edges with w >= 0."""
    INF = float("inf")
    dist = [INF] * len(graph)
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:                         # a shorter path was found later
            continue
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return [-1 if x == INF else x for x in dist]

#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

using Graph = vector<vector<pair<int, long long>>>;   // graph[u] = {(v, w), ...}, w >= 0

// Shortest distance from source to every node, or -1 if unreachable.
vector<long long> dijkstra(const Graph& graph, int source) {
    const long long INF = numeric_limits<long long>::max();
    vector<long long> dist(graph.size(), INF);
    dist[source] = 0;
    // min-heap of (distance, node)
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> heap;
    heap.push({0, source});
    while (!heap.empty()) {
        auto [d, u] = heap.top();
        heap.pop();
        if (d > dist[u]) {                           // a shorter path was found later
            continue;
        }
        for (auto [v, w] : graph[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                heap.push({dist[v], v});
            }
        }
    }
    for (auto& x : dist) if (x == INF) x = -1;
    return dist;
}

import java.util.*;

class Dijkstra {
    // graph.get(u) holds edges {v, w} with w >= 0.
    // Returns the shortest distance from source to every node, or -1 if unreachable.
    static long[] shortestPaths(List<List<int[]>> graph, int source) {
        long[] dist = new long[graph.size()];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[source] = 0;
        // min-heap of {distance, node}
        PriorityQueue<long[]> heap = new PriorityQueue<>(
            (x, y) -> x[0] != y[0] ? Long.compare(x[0], y[0]) : Long.compare(x[1], y[1]));
        heap.add(new long[] {0, source});
        while (!heap.isEmpty()) {
            long[] top = heap.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) {                        // a shorter path was found later
                continue;
            }
            for (int[] edge : graph.get(u)) {
                int v = edge[0], w = edge[1];
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    heap.add(new long[] {dist[v], v});
                }
            }
        }
        for (int i = 0; i < dist.length; i++) {
            if (dist[i] == Long.MAX_VALUE) dist[i] = -1;
        }
        return dist;
    }
}

A negative edge breaks that argument. Take edges S → A costing 2, S → B costing 5 and B → A costing −4. Dijkstra settles A at 2, but the real shortest path S → B → A costs 1. The textbook version, which never revisits a settled node, returns 2. The lazy code above happens to recover here by re-processing A, but on bigger graphs that re-processing can take exponential time. Either way the guarantee is gone, so use Bellman-Ford when weights can be negative.

Why it’s O((V + E) log V)

Each successful relaxation pushes one entry, so there are at most E + 1 pushes and at most E + 1 pops. A heap operation on up to E entries costs O(log E), and since E ≤ V², that’s the same as O(log V).

Each node is settled once, and only then are its edges scanned, so the edge loops do E relaxations in total. Stale entries are popped and dropped without touching any edges.

Space is O(V) for dist plus O(E) for the heap, which can hold several entries for the same node.

Common mistakes

if v not in seen: seen.add(v); push(...)   # ✗ locks in the first path
if d + w < dist[v]: dist[v] = d + w; push(...)   # ✓ keep improving until popped

d, u = heappop(heap)                      # ✗ then relaxes from old entries too
if d > dist[u]: continue                  # ✓ skip entries that were beaten

vector<int> dist(n, INT_MAX);        // ✗ d + w overflows
vector<long long> dist(n, LLONG_MAX); // ✓ and only add to finite distances

Variations

• Path reconstruction. Store parent[v] = u whenever dist[v] improves. To get the path to a target, follow parent back to the source and reverse it.
• Stop early at a target. If you only need one destination, return as soon as it is popped with a non-stale entry. Its distance is already final.
• 0-1 BFS. When every weight is 0 or 1, replace the heap with a deque: push to the front for weight 0 and to the back for weight 1. That’s O(V + E).
• Bellman-Ford handles negative weights and detects negative cycles, at O(V · E). Use it when Dijkstra’s assumption fails.
• A* search adds an estimate of the remaining distance to each heap key, so the search heads toward the target first. With an estimate that never overshoots, it still finds the shortest path, usually after exploring far fewer nodes.