☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Djisktra's Algorithm

Hard TUF ID 2827 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an undirected weighted graph with V vertices numbered 0 to V - 1 and a list of edges {u, v, w}, each an edge between u and v of weight w ≥ 0. Given a source vertex src, return the length of the shortest path from src to every vertex. The original statement guarantees a connected graph; the code here also handles disconnected graphs by reporting -1 for unreachable vertices.

Constraints: 1 ≤ V ≤ 10^5, 0 ≤ w ≤ 1000, no negative weights. (The sheet spells the name “Djisktra”; the algorithm is Edsger Dijkstra’s.)

Example 1

V = 3, src = 2, edges = [0-1 (1), 0-2 (6), 1-2 (3)]
answer = [4, 3, 0]       // 2 → 1 → 0 costs 3 + 1 = 4, cheaper than the direct edge of 6

Example 2

V = 6, src = 0
edges = [0-1 (4), 0-2 (4), 1-2 (2), 2-3 (3), 2-4 (1), 2-5 (6), 3-5 (2), 4-5 (3)]
answer = [0, 4, 4, 7, 5, 8]   // node 5 via 0-2-4-5 = 4 + 1 + 3

Every approach below stores the graph as an adjacency list of {neighbour, weight} pairs, with each undirected edge added in both directions, and finishes by turning the “infinity” marker into -1:

static List<List<int[]>> buildAdj(int V, int[][] edges) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(new int[]{e[1], e[2]});
        adj.get(e[1]).add(new int[]{e[0], e[2]});
    }
    return adj;
}

/** Replaces the "infinity" marker with -1 for unreachable nodes. */
static int[] finish(int[] dist) {
    for (int i = 0; i < dist.length; i++) if (dist[i] == Integer.MAX_VALUE) dist[i] = -1;
    return dist;
}

Approach 1: Brute force, relax until stable

Intuition. Shortest distances satisfy dist[v] ≤ dist[u] + w for every edge. Start from dist[src] = 0 and infinity elsewhere, and keep sweeping over all edges, lowering any dist[v] that breaks the rule, until a full sweep changes nothing. Each sweep makes at least one more edge of every shortest path correct, so at most V - 1 productive sweeps happen.

Algorithm.

  1. Initialise dist.
  2. While the previous sweep changed something: for every edge, in both directions, relax it if the tail is reachable.
  3. Return dist, with infinity mapped to -1.
static int[] bruteForce(int V, int[][] edges, int src) {
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int[] e : edges) {
            for (int d = 0; d < 2; d++) {
                int u = e[d], v = e[1 - d];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + e[2] < dist[v]) {
                    dist[v] = dist[u] + e[2];
                    changed = true;
                }
            }
        }
    }
    return finish(dist);
}

Complexity. Time O(V × E): up to V sweeps, each over all edges. Space O(V). This is Bellman-Ford, and it is wasteful here because it never uses the fact that the weights are non-negative.

Approach 2: Better, Dijkstra with an array

Intuition. Split the vertices into finished ones, whose distance is known for sure, and the rest, which only have a tentative distance through finished vertices. The greedy step is: the unfinished vertex u with the smallest tentative distance is already correct.

Why? Consider any path from src to u. It starts inside the finished set and must leave it at some first unfinished vertex x. The part of the path up to x costs at least dist[x], and dist[x] ≥ dist[u] because u was chosen as the smallest. The rest of the path, from x to u, has non-negative weights and cannot make it cheaper. So no path beats dist[u], and u can be marked finished. Then we relax u’s edges, which may lower the tentative distances of its neighbours, and repeat.

The simplest way to find the smallest unfinished vertex is a linear scan.

Algorithm.

  1. Initialise dist, and done[] as all false.
  2. Repeat V times: scan for the unfinished vertex u with the smallest finite distance. If there is none, stop.
  3. Mark u done and relax each edge u - v with v not done.
static int[] dijkstraArray(int V, int[][] edges, int src) {
    List<List<int[]>> adj = buildAdj(V, edges);
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    boolean[] done = new boolean[V];
    for (int iter = 0; iter < V; iter++) {
        int u = -1;
        for (int i = 0; i < V; i++) {
            if (!done[i] && dist[i] != Integer.MAX_VALUE && (u == -1 || dist[i] < dist[u])) u = i;
        }
        if (u == -1) break;                               // every remaining node is unreachable
        done[u] = true;                                   // dist[u] is final from here on
        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            if (!done[v] && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
    }
    return finish(dist);
}

Complexity. Time O(V^2 + E): V scans of V vertices, and each edge is relaxed a constant number of times. Space O(V + E). This version is actually the best choice for dense graphs where E is close to V^2, because then the heap’s log factor buys nothing.

Approach 3: Optimal, Dijkstra with a priority queue

Intuition. For sparse graphs, the linear scan dominates. Replace it with a min-heap of {distance, vertex} pairs so the closest vertex is found in O(log V).

Java’s PriorityQueue cannot lower the key of an element already inside it. The standard workaround is lazy deletion: when dist[v] improves, push a new pair {dist[v], v} and leave the old one in the heap. When an old pair is popped later, its distance is larger than dist[v], so it is stale and we skip it. The first pair popped for each vertex carries its final distance, by the same greedy argument as in Approach 2.

Algorithm.

  1. Initialise dist, push {0, src}.
  2. Pop the pair {d, u} with the smallest d. If d > dist[u], skip it.
  3. For each edge u - v of weight w, if d + w < dist[v], set dist[v] = d + w and push {dist[v], v}.
  4. When the heap is empty, dist is final.
static int[] optimal(int V, int[][] edges, int src) {
    List<List<int[]>> adj = buildAdj(V, edges);
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.add(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int d = top[0], u = top[1];
        if (d > dist[u]) continue;                        // stale entry: u was settled with a smaller distance
        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.add(new int[]{dist[v], v});
            }
        }
    }
    return finish(dist);
}

Dry run on Example 2 from src = 0. Pairs with equal distance may pop in either order; the result is the same.

pop action pushed
(0, 0) dist1 = 4, dist2 = 4 (4, 1), (4, 2)
(4, 1) 0 and 2 are not improved none
(4, 2) dist3 = 7, dist4 = 5, dist5 = 10 (7, 3), (5, 4), (10, 5)
(5, 4) dist5 = 8 (8, 5)
(7, 3) 5 via 3 would be 9, no change none
(8, 5) no neighbour improves none
(10, 5) stale: 10 > dist5 = 8, skipped none

Result [0, 4, 4, 7, 5, 8]. The pair (10, 5) shows lazy deletion at work: it was made obsolete by (8, 5) and is discarded in O(1) after being popped.

Complexity. Each vertex is expanded once (later copies are stale), so each direction of each edge is relaxed at most once and the heap receives at most 2E + 1 pairs. Each push or pop costs O(log E) = O(log V) because E ≤ V^2. Total time O((V + E) log V). Space O(V + E) for the graph, distances and heap.

Edge cases and pitfalls