Dijkstra's algorithm

Shortest paths from one place to all others when no edge has a negative length. Repeatedly settle the closest place not yet settled, then see whether going through it shortens the way to its neighbours.

Time (binary heap)	Extra space	Needs
\(O((V + E) \log V)\)	\(O(V + E)\)	every edge weight \(\ge 0\)

The idea

Imagine water spreading from the start along every road at the same speed. It reaches places in order of their true distance. Dijkstra's algorithm simulates this without the water.

Keep a best-known distance for every place: 0 for the start, \(\infty\) for the rest. Then repeat:

1. Pick the unsettled place with the smallest known distance and settle it: its distance is now final.
2. For each road from it, check whether going through it is shorter than the best-known way to the other end (relaxing the edge): if dist[u] + w < dist[v]: dist[v] = dist[u] + w.

Why is the closest unsettled place final? Any other route to it would have to leave the settled region through some unsettled place that is already at least as far away, and with no negative roads the rest of that route cannot make it shorter. This is exactly where negative weights break the method.

A min-heap finds the closest unsettled place quickly. Instead of updating entries inside the heap, the code pushes a new entry and skips stale ones when they come out.

The demo uses real places on Mars, with roads as long as the true distances between them, the same network as the picture on the home page.

How it works

1. dist = [∞, ...], dist[src] = 0; heap = [(0, src)].
2. While the heap is not empty: pop (d, u); if d > dist[u], skip it (stale). Otherwise, for each edge u → v of weight w, if d + w < dist[v], set dist[v] = d + w, parent[v] = u, and push (dist[v], v).

Code

PythonJavaC++

import heapq

PLACES = ["Erebus Montes", "Olympus Mons", "Ascraeus Mons", "Valles Marineris", "Elysium Mons",
          "Utopia Planitia", "Gale crater", "Jezero crater", "Hellas Planitia"]
# roads between real places on Mars, with their great-circle lengths in km
ROADS = [(0, 1, 2369), (0, 4, 2016), (0, 5, 2305), (1, 2, 1740), (2, 3, 3043), (4, 6, 1879), (5, 4, 1486),
         (5, 7, 3214), (7, 6, 3782), (7, 8, 3616), (6, 8, 4122), (1, 6, 5337)]


def dijkstra(adj, src):
    """Shortest distances from src when every edge weight is >= 0, and each vertex's parent."""
    INF = float("inf")
    dist = [INF] * len(adj)
    parent = [-1] * len(adj)
    dist[src] = 0
    pq = [(0, src)]                          # (distance found so far, vertex)
    while pq:
        d, u = heapq.heappop(pq)             # the closest vertex not yet settled
        if d > dist[u]:
            continue                         # an old, longer entry: skip it
        for v, w in adj[u]:
            if d + w < dist[v]:              # relax: going through u is shorter
                dist[v] = d + w
                parent[v] = u
                heapq.heappush(pq, (dist[v], v))
    return dist, parent


def route(parent, t):
    out = []
    while t != -1:
        out.append(t)
        t = parent[t]
    return out[::-1]


if __name__ == "__main__":
    adj = [[] for _ in PLACES]
    for u, v, w in ROADS:
        adj[u].append((v, w))
        adj[v].append((u, w))
    dist, parent = dijkstra(adj, 0)
    for v, name in enumerate(PLACES):
        print(f"{name}: {dist[v]} km via {' > '.join(PLACES[x] for x in route(parent, v))}")

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Dijkstra {
    static final String[] PLACES = {"Erebus Montes", "Olympus Mons", "Ascraeus Mons", "Valles Marineris",
        "Elysium Mons", "Utopia Planitia", "Gale crater", "Jezero crater", "Hellas Planitia"};
    // roads between real places on Mars, with their great-circle lengths in km
    static final int[][] ROADS = {{0, 1, 2369}, {0, 4, 2016}, {0, 5, 2305}, {1, 2, 1740}, {2, 3, 3043},
        {4, 6, 1879}, {5, 4, 1486}, {5, 7, 3214}, {7, 6, 3782}, {7, 8, 3616}, {6, 8, 4122}, {1, 6, 5337}};

    /** Shortest distances from src when every edge weight is >= 0; fills parent[]. */
    static long[] dijkstra(List<List<int[]>> adj, int src, int[] parent) {
        long[] dist = new long[adj.size()];
        Arrays.fill(dist, Long.MAX_VALUE);
        Arrays.fill(parent, -1);
        dist[src] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.add(new long[]{0, src});                   // (distance found so far, vertex)
        while (!pq.isEmpty()) {
            long[] top = pq.poll();                   // the closest vertex not yet settled
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) continue;                // an old, longer entry: skip it
            for (int[] e : adj.get(u)) {
                int v = e[0], w = e[1];
                if (d + w < dist[v]) {                // relax: going through u is shorter
                    dist[v] = d + w;
                    parent[v] = u;
                    pq.add(new long[]{dist[v], v});
                }
            }
        }
        return dist;
    }

    static List<Integer> route(int[] parent, int t) {
        List<Integer> out = new ArrayList<>();
        for (; t != -1; t = parent[t]) out.add(t);
        Collections.reverse(out);
        return out;
    }

    public static void main(String[] args) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < PLACES.length; i++) adj.add(new ArrayList<>());
        for (int[] r : ROADS) { adj.get(r[0]).add(new int[]{r[1], r[2]}); adj.get(r[1]).add(new int[]{r[0], r[2]}); }
        int[] parent = new int[PLACES.length];
        long[] dist = dijkstra(adj, 0, parent);
        for (int v = 0; v < PLACES.length; v++) {
            List<String> names = new ArrayList<>();
            for (int x : route(parent, v)) names.add(PLACES[x]);
            System.out.println(PLACES[v] + ": " + dist[v] + " km via " + String.join(" > ", names));
        }
    }
}

#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;

const vector<string> PLACES = {"Erebus Montes", "Olympus Mons", "Ascraeus Mons", "Valles Marineris",
    "Elysium Mons", "Utopia Planitia", "Gale crater", "Jezero crater", "Hellas Planitia"};
// roads between real places on Mars, with their great-circle lengths in km
const vector<vector<int>> ROADS = {{0, 1, 2369}, {0, 4, 2016}, {0, 5, 2305}, {1, 2, 1740}, {2, 3, 3043},
    {4, 6, 1879}, {5, 4, 1486}, {5, 7, 3214}, {7, 6, 3782}, {7, 8, 3616}, {6, 8, 4122}, {1, 6, 5337}};

// Shortest distances from src when every edge weight is >= 0; fills parent.
vector<long long> dijkstra(const vector<vector<pair<int, int>>>& adj, int src, vector<int>& parent) {
    vector<long long> dist(adj.size(), LLONG_MAX);
    parent.assign(adj.size(), -1);
    dist[src] = 0;
    // (distance found so far, vertex), smallest first
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();            // the closest vertex not yet settled
        if (d > dist[u]) continue;                   // an old, longer entry: skip it
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {                   // relax: going through u is shorter
                dist[v] = d + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

vector<int> route(const vector<int>& parent, int t) {
    vector<int> out;
    for (; t != -1; t = parent[t]) out.push_back(t);
    reverse(out.begin(), out.end());
    return out;
}

int main() {
    vector<vector<pair<int, int>>> adj(PLACES.size());
    for (auto& r : ROADS) { adj[r[0]].push_back({r[1], r[2]}); adj[r[1]].push_back({r[0], r[2]}); }
    vector<int> parent;
    auto dist = dijkstra(adj, 0, parent);
    for (size_t v = 0; v < PLACES.size(); v++) {
        cout << PLACES[v] << ": " << dist[v] << " km via ";
        auto r = route(parent, v);
        for (size_t i = 0; i < r.size(); i++) cout << (i ? " > " : "") << PLACES[r[i]];
        cout << "\n";
    }
}

Output (one line per place):

Erebus Montes: 0 km via Erebus Montes
Olympus Mons: 2369 km via Erebus Montes > Olympus Mons
Ascraeus Mons: 4109 km via Erebus Montes > Olympus Mons > Ascraeus Mons
Valles Marineris: 7152 km via Erebus Montes > Olympus Mons > Ascraeus Mons > Valles Marineris
Elysium Mons: 2016 km via Erebus Montes > Elysium Mons
Utopia Planitia: 2305 km via Erebus Montes > Utopia Planitia
Gale crater: 3895 km via Erebus Montes > Elysium Mons > Gale crater
Jezero crater: 5519 km via Erebus Montes > Utopia Planitia > Jezero crater
Hellas Planitia: 8017 km via Erebus Montes > Elysium Mons > Gale crater > Hellas Planitia

The direct road from Olympus Mons to Gale crater (5,337 km) is never used: going round by Elysium Mons is shorter.

When to use it

• Road maps and navigation (with refinements such as A* and contraction hierarchies), network routing (the OSPF protocol runs Dijkstra on every router), flight connections with travel times.
• Any "cheapest way" problem with non-negative costs: the fewest coins of energy, the least risk.
• Grids with different terrain costs, games' path-finding.
• Not with negative weights: use Bellman-Ford.

Common mistakes

• Negative edges: the answer is silently wrong.
• Not skipping stale heap entries: still correct but slower; with if d > dist[u]: continue each vertex is expanded once.
• Overflow: start distances at a large value and use 64-bit sums; INT_MAX + w wraps around in Java and C++.
• Stopping too early: for one target, you may stop when the target is popped, not when it is first reached.
• Using it for the longest path: negating weights makes them negative, which Dijkstra cannot handle.

Going deeper

Each part below starts closed; open the ones you want.

Sample walkthrough: from Erebus Montes

Settle (distance)	Improvements
Erebus Montes (0)	Olympus 2,369 · Elysium 2,016 · Utopia 2,305
Elysium Mons (2,016)	Gale 2,016 + 1,879 = 3,895 (Utopia: 2,016 + 1,486 = 3,502, worse than 2,305)
Utopia Planitia (2,305)	Jezero 2,305 + 3,214 = 5,519
Olympus Mons (2,369)	Ascraeus 4,109 (Gale via Olympus: 7,706, worse)
Gale crater (3,895)	Hellas 3,895 + 4,122 = 8,017 (Jezero via Gale: 7,677, worse)
Ascraeus Mons (4,109)	Valles 7,152
Jezero crater (5,519)	(Hellas via Jezero: 9,135, worse)
Valles Marineris (7,152)	—
Hellas Planitia (8,017)	—

The math: correctness and running time

Let \(\delta(v)\) be the true shortest distance and \(S\) the set of settled vertices.

Invariant. For every \(v \in S\), \(\text{dist}[v] = \delta(v)\); for every \(v \notin S\), \(\text{dist}[v]\) is the shortest path to \(v\) whose vertices, apart from \(v\), all lie in \(S\).

Proof that the next settled vertex is correct. Let \(u\) be the unsettled vertex with the smallest \(\text{dist}\). Take any path \(P\) from \(s\) to \(u\), and let \(y\) be the first vertex on it outside \(S\). Then

\[ \text{len}(P) \;\ge\; \delta_{S}(y) \;=\; \text{dist}[y] \;\ge\; \text{dist}[u], \]

because the part of \(P\) after \(y\) has length \(\ge 0\) (this is where non-negative weights are used), the part up to \(y\) is a path through \(S\), and \(u\) was chosen with the smallest \(\text{dist}\). So no path beats \(\text{dist}[u]\), and \(\text{dist}[u] = \delta(u)\).

Running time with a binary heap: at most \(E\) pushes and pops, each \(O(\log E) = O(\log V)\) (since \(E < V^2\)), plus \(O(V + E)\) for scanning lists:

\[ T = O\big((V + E)\log V\big). \]

With a Fibonacci heap (decrease-key in \(O(1)\) amortized), \(O(E + V \log V)\). With a plain array and no heap, \(O(V^2)\), which is better for very dense graphs.

Great-circle distances used in the demo: for latitudes \(\varphi_1, \varphi_2\) and longitude difference \(\Delta\lambda\), the central angle is \(\theta = \arccos(\sin\varphi_1 \sin\varphi_2 + \cos\varphi_1 \cos\varphi_2 \cos\Delta\lambda)\), and the distance is \(R\theta\) with Mars's mean radius \(R = 3389.5\) km.

Watch it step by step

Numbers above places are the best-known distances in km. Orange is the place being settled, green the settled ones, blue those waiting in the heap; red roads just improved a distance.

Variations and related ideas

• A* search adds a guess of the remaining distance (for maps, the straight-line distance) to steer the search towards the target; with a guess that never overestimates, it still finds a shortest path, usually after exploring far fewer vertices.
• Bidirectional Dijkstra searches from both ends.
• Contraction hierarchies precompute shortcuts so that continental road networks answer queries in milliseconds.
• Johnson's algorithm reweights a graph with negative edges (using Bellman-Ford once) so that Dijkstra can run from every vertex: all pairs in \(O(VE \log V)\).
• Widest path / most reliable path: the same scheme with max-min or products instead of sums.

See also

• Breadth-first search: the unweighted case
• Bellman-Ford: negative weights
• Binary heap
• Prim's algorithm: almost the same code, a different question

References

• E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik 1, 1959.
• T. H. Cormen et al., Introduction to Algorithms, 4th ed., §22.3 (Dijkstra's algorithm).
• P. E. Hart, N. J. Nilsson, B. Raphael, "A formal basis for the heuristic determination of minimum cost paths", IEEE Transactions on Systems Science and Cybernetics 4(2), 1968 (A*).
• Place coordinates: USGS Gazetteer of Planetary Nomenclature.