4.3.6.1 - Dijkstra's shortest-path algorithm (Java)

Tentative distances and finalised vertices

Dijkstra's algorithm finds minimum-total-weight routes from a start vertex when all edge weights are non-negative.

An edge weight might represent travel time, distance or a communication cost. Fewest edges is not necessarily least total weight. Initially the start distance is0 and all others are infinity, meaning no route has yet been found. Infinity is a state, not a very long measured route.

Use this supplied algorithm throughout the lesson:

1. Select the unfinalised vertex with the smallest finite tentative distance; ties use alphabetical order. Stop if none exists.
2. Finalise that vertex u. For every unfinalised neighbour v, calculate distance(u)+weight(u,v). If this is smaller than distance(v), replace distance(v) and record u as v's predecessor.
3. Repeat until all reachable vertices are finalised, or until the required destination is finalised if only its shortest route is needed.

[DIAGRAM: asset_slug: dijkstra_graph; description: Non-negative weighted graph with edges A–B4, A–C1, B–C2, B–D5, C–D8, C–E10 and D–E2.]

The graph is undirected, with exactly the edges listed in the caption. Starting at A, the first selection finalises A0 and sets B4,C1. Select C next, since1 is smaller than4. Taking B before C simply because it was discovered first would not follow the supplied algorithm. Non-negative weights mean a route through a later, no-cheaper vertex cannot make an already finalised distance smaller. Negative weights invalidate that reasoning; this lesson does not apply Dijkstra to them.

Relaxing weighted edges

Relaxation tests whether a newly considered route improves a neighbour's current tentative distance.

After C1 is selected, the route A–C–B costs1+2=3, improving B4. C also offers D9 and E11. B3 then offers D8, improving D9. D8 offers E10, improving E11. Do not replace a smaller distance with a worse candidate or add a weight to an unreachable infinity value.

This supplied Java implementation belongs inside a class with import java.util.Arrays;. weight[u][v] is−1 for no edge and a non-negative integer otherwise. Indices are valid; all finite path sums fit below Integer.MAX_VALUE. Scanning indices in increasing order and replacing the selection only on a strict improvement gives lowest-index ties.

static int[] distances(int[][] weight, int start) {
    int n = weight.length;
    int[] d = new int[n];
    Arrays.fill(d, Integer.MAX_VALUE);
    boolean[] done = new boolean[n];
    d[start] = 0;
    while (true) {
        int u = -1;
        int best = Integer.MAX_VALUE;
        for (int v = 0; v < n; v++) {
            if (!done[v] && d[v] < best) {
                u = v;
                best = d[v];
            }
        }
        if (u == -1) break;
        done[u] = true;
        for (int v = 0; v < n; v++) {
            if (!done[v] && weight[u][v] >= 0) {
                int candidate = d[u] + weight[u][v];
                if (candidate < d[v]) d[v] = candidate;
            }
        }
    }
    return d;
}

Only finite vertices are selected, so the addition never starts from infinity. A zero-weight edge is valid and must not be confused with no edge. An unreachable vertex stays at the sentinel value when selection stops.