Shortest Paths

Choosing the algorithm

Four algorithms cover essentially every shortest-path problem. Which one you need is decided by the edge weights and the number of sources — not by preference.

Which shortest-path algorithm

The first row is worth emphasising: if every edge costs the same, Dijkstra is unnecessary overhead. Plain BFS is simpler and faster. See Graph Representation and Traversal.

Dijkstra

For non-negative weights from a single source. Repeatedly settle the closest unsettled node, then relax its outgoing edges.

static class Edge {
    int to;
    long weight;
    Edge(int to, long weight) { this.to = to; this.weight = weight; }
}

static long[] dijkstra(List<List<Edge>> adj, int source, int n) {
    long[] dist = new long[n + 1];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[source] = 0;

    // {node, distance}, ordered by distance
    PriorityQueue<long[]> pq =
        new PriorityQueue<>((x, y) -> Long.compare(x[1], y[1]));
    pq.add(new long[]{source, 0});

    while (!pq.isEmpty()) {
        long[] top = pq.poll();
        int u = (int) top[0];
        long d = top[1];

        if (d > dist[u]) continue;      // a stale copy — already settled better

        for (Edge e : adj.get(u)) {
            long nd = d + e.weight;
            if (nd < dist[e.to]) {
                dist[e.to] = nd;
                pq.add(new long[]{e.to, nd});
            }
        }
    }
    return dist;
}

if (d > dist[u]) continue;

Other details that matter:

• dist is long and initialised to Long.MAX_VALUE. Using Integer.MAX_VALUE with int overflows the moment you add a weight to it.
• Test nd < dist[e.to] before assigning, not after.
• Unreachable nodes keep Long.MAX_VALUE. Check for that before printing rather than printing a huge number.

Dijkstra requires non-negative weights. With a negative edge it can settle a node too early and never revisit it, producing a wrong answer with no error.

0-1 BFS

When every weight is 0 or 1, a deque replaces the heap and the log factor disappears. Push zero-weight moves to the front and one-weight moves to the back, which keeps the deque sorted by distance automatically.

static int[] zeroOneBfs(List<List<Edge>> adj, int source, int n) {
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    Deque<Integer> dq = new ArrayDeque<>();
    dq.addFirst(source);

    while (!dq.isEmpty()) {
        int u = dq.pollFirst();
        for (Edge e : adj.get(u)) {
            int nd = dist[u] + (int) e.weight;
            if (nd < dist[e.to]) {
                dist[e.to] = nd;
                if (e.weight == 0) dq.addFirst(e.to);
                else               dq.addLast(e.to);
            }
        }
    }
    return dist;
}

This turns up in grid problems where some moves are free and others cost one — for example, walking is free but breaking a wall costs one.

Bellman–Ford

Handles negative weights. Relax every edge V - 1 times; any distance that can still improve on an extra pass lies on a negative cycle.

static long[] bellmanFord(int[][] edges, int source, int n) {
    long[] dist = new long[n + 1];
    Arrays.fill(dist, Long.MAX_VALUE / 4);   // headroom so adding cannot overflow
    dist[source] = 0;

    for (int iter = 0; iter < n - 1; iter++) {
        boolean changed = false;
        for (int[] e : edges) {              // {from, to, weight}
            if (dist[e[0]] + e[2] < dist[e[1]]) {
                dist[e[1]] = dist[e[0]] + e[2];
                changed = true;
            }
        }
        if (!changed) break;                 // settled early
    }
    return dist;
}

Two practical notes. Initialising to Long.MAX_VALUE / 4 rather than Long.MAX_VALUE means dist[from] + weight cannot overflow for an unreachable node. And the changed flag often ends the loop far before V - 1 iterations.

To detect a negative cycle, run one more pass; if anything still improves, a negative cycle is reachable from the source.

Floyd–Warshall

All pairs at once, for small graphs. Three nested loops, with the intermediate node outermost.

static void floydWarshall(long[][] dist, int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

Reconstructing the path

Distances alone are often not the answer. Record where each improvement came from.

int[] parent = new int[n + 1];
Arrays.fill(parent, -1);

// inside the relaxation:
if (nd < dist[e.to]) {
    dist[e.to] = nd;
    parent[e.to] = u;
    pq.add(new long[]{e.to, nd});
}

// afterwards, walk backwards from the target
List<Integer> path = new ArrayList<>();
for (int at = target; at != -1; at = parent[at]) {
    path.add(at);
}
Collections.reverse(path);

Related