☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Dijkstra's algorithm

Hard TUF ID 520 SDE

Java source ↗ Edit this article ↗

Problem

You are given an undirected weighted graph with V vertices numbered 0 to V - 1, a list of edges {u, v, w} with non-negative weights w, and a source vertex src. Return an array whose i-th entry is the length of the shortest path from src to vertex i. The sheet’s version (GFG, “Implementing Dijkstra Algorithm”) passes an adjacency list and promises a connected graph; here the input is an edge list and any vertex that cannot be reached gets -1, so the code also works on disconnected graphs.

Constraints: weights are non-negative integers of moderate size (around 10^3), and V and E can be large enough that an O((V + E) log V) solution is expected.

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 = 5, src = 0
edges = [0-1 (2), 0-2 (4), 1-2 (1), 1-3 (7), 2-4 (3), 3-4 (1)]
answer = [0, 2, 3, 7, 6] // vertex 3 via 0-1-2-4-3 = 2 + 1 + 3 + 1 = 7, not via the edge 1-3 (total 9)

Every approach uses the same two helpers: an adjacency list of {neighbour, weight} pairs (each undirected edge stored in both directions), and a final step that turns 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;
}

/** Turns the "infinity" marker into -1 for vertices that were never reached. */
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, try every simple path

Intuition. The shortest distance is, by definition, the minimum over all paths. With non-negative weights a shortest path never has to repeat a vertex: a repeated vertex means the path contains a cycle, and cutting out a cycle of weight ≥ 0 never makes the path longer. So it is enough to enumerate simple paths. A DFS from src that marks the vertices on the current path, records the arrival cost at each vertex, and unmarks on the way back does exactly that.

Algorithm.

  1. Set best[v] = ∞ for all v.
  2. explore(u, d): update best[u] with d, mark u as on the path, recurse into every neighbour not on the path with cost d + w, then unmark u.
  3. Call explore(src, 0) and convert ∞ to -1.
static int[] bruteForce(int V, int[][] edges, int src) {
    List<List<int[]>> adj = buildAdj(V, edges);
    int[] best = new int[V];
    Arrays.fill(best, Integer.MAX_VALUE);
    boolean[] onPath = new boolean[V];
    explore(src, 0, adj, onPath, best);
    return finish(best);
}

static void explore(int u, int d, List<List<int[]>> adj, boolean[] onPath, int[] best) {
    best[u] = Math.min(best[u], d);
    onPath[u] = true;
    for (int[] e : adj.get(u)) {
        if (!onPath[e[0]]) explore(e[0], d + e[1], adj, onPath, best);
    }
    onPath[u] = false;                                     // backtrack so other paths may pass through u
}

Complexity. Time is exponential: a complete graph on V vertices has about (V - 2)! simple paths between two vertices, already millions for V = 12. Space O(V) for the recursion and the onPath array. The waste is that the DFS keeps re-exploring a vertex through different histories even though only the cheapest arrival at that vertex matters for what comes after.

Approach 2: Better, Dijkstra with an array

Intuition. Grow a set of settled vertices whose distance is final. At the start only src has a known distance, 0. The claim that drives the algorithm: among unsettled vertices, the one with the smallest tentative distance d can be settled immediately. Any other route to it must leave the settled region through some unsettled vertex x, whose tentative distance is already ≥ d, and every remaining edge on that route adds a weight ≥ 0, so the route costs at least d. After settling a vertex u, relax its edges: for each neighbour v, set dist[v] = min(dist[v], dist[u] + w).

This argument is the exact place where non-negative weights are needed. A negative edge after x could make the detour cheaper, which is why Dijkstra fails on negative weights.

Algorithm.

  1. dist[src] = 0, everything else ∞; no vertex is settled.
  2. Repeat up to V times: scan for the unsettled vertex u with the smallest finite dist. If none exists, stop (the rest is unreachable).
  3. Settle u and relax every edge u - v whose other end is unsettled.
static int[] better(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[] settled = new boolean[V];
    for (int iter = 0; iter < V; iter++) {
        int u = -1;
        for (int i = 0; i < V; i++) {
            if (!settled[i] && dist[i] != Integer.MAX_VALUE && (u == -1 || dist[i] < dist[u])) u = i;
        }
        if (u == -1) break;                                // everything left is unreachable
        settled[u] = true;                                 // dist[u] can no longer improve
        for (int[] e : adj.get(u)) {
            int v = e[0];
            if (!settled[v] && dist[u] + e[1] < dist[v]) dist[v] = dist[u] + e[1];
        }
    }
    return finish(dist);
}

Complexity. Time O(V^2 + E): V scans of O(V) each, and every edge is relaxed a constant number of times. Space O(V + E). This is the right choice for very dense graphs, where E is close to V^2 and a heap would only add a log factor. For sparse graphs the repeated scan is the bottleneck.

Approach 3: Optimal, Dijkstra with a priority queue

Intuition. Replace the linear scan with a min-heap keyed by tentative distance, so the closest unsettled vertex comes out in O(log V). Java’s PriorityQueue has no “decrease key” operation, so whenever dist[v] improves we simply push a new entry {newDist, v} and leave the old one inside. When an entry pops whose distance is larger than the current dist[u], it is stale (a better entry for u was already processed), and we skip it. This is called lazy deletion.

Algorithm.

  1. dist[src] = 0, push {0, src}.
  2. While the heap is not empty: pop {d, u}. If d > dist[u], skip it.
  3. Otherwise relax each edge u - v: if d + w < dist[v], update dist[v] and push {d + w, v}.
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]));   // {distance, vertex}
    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], nd = d + e[1];
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.add(new int[]{nd, v});
            }
        }
    }
    return finish(dist);
}

Dry run on Example 2 (src = 0):

Pop Stale? Improvements pushed dist after
{0, 0} no 1 → 2, 2 → 4 [0, 2, 4, ∞, ∞]
{2, 1} no 2 → 3, 3 → 9 [0, 2, 3, 9, ∞]
{3, 2} no 4 → 6 [0, 2, 3, 9, 6]
{4, 2} yes, 4 > 3 none unchanged
{6, 4} no 3 → 7 [0, 2, 3, 7, 6]
{7, 3} no none unchanged
{9, 3} yes, 9 > 7 none final [0, 2, 3, 7, 6]

Complexity. Every successful relaxation pushes one entry, so the heap holds O(E) entries and 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).

Approach 4: Optimal variant, a TreeSet with real deletion

Intuition. An ordered set can remove any element, so when dist[v] improves we erase the old pair {dist[v], v} before inserting the new one. The set never holds stale entries and has at most one entry per vertex. This is the C++ set version that is often taught alongside the heap version. The comparator must break ties by vertex number: if two vertices with equal distance compared as equal, TreeSet would treat them as duplicates and silently drop one.

static int[] optimalSet(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;
    TreeSet<int[]> set = new TreeSet<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
    set.add(new int[]{0, src});
    while (!set.isEmpty()) {
        int[] top = set.pollFirst();
        int d = top[0], u = top[1];
        for (int[] e : adj.get(u)) {
            int v = e[0], nd = d + e[1];
            if (nd < dist[v]) {
                if (dist[v] != Integer.MAX_VALUE) set.remove(new int[]{dist[v], v});   // drop the outdated entry
                dist[v] = nd;
                set.add(new int[]{nd, v});
            }
        }
    }
    return finish(dist);
}

Complexity. Also O((V + E) log V) time, O(V + E) space. In Java the heap version is usually faster in practice because PriorityQueue is an array-backed heap with small constants, while every TreeSet operation walks and rebalances a red-black tree.

Edge cases and pitfalls