Shortest Paths — Getting There With Minimum Cost

Shortest path algorithms are among the most practically useful algorithms in computer science. Every time a navigation app routes you around traffic, every time a network packet finds its way across the internet, every time a game character pathfinds around obstacles, a shortest path algorithm is running. Learning these four algorithms gives you the tools to solve an entire class of real problems.

The selection logic is simple: the algorithm you use depends entirely on what your graph looks like. No negative edges? Dijkstra. Negative edges, need to detect negative cycles? Bellman-Ford. All-pairs distances on a small graph? Floyd-Warshall. Edge weights only 0 or 1? 0-1 BFS.

Dijkstra’s Algorithm

Dijkstra solves single-source shortest paths on graphs with non-negative edge weights. It’s a greedy algorithm: at each step, it permanently settles the unvisited node closest to the source, then relaxes its edges.

Core idea: maintain a dist[] array initialized to infinity. Set dist[source] = 0. Always process the node with the current smallest tentative distance. When you settle a node, its distance is final — no shorter path to it will be found later (because all edge weights are non-negative, future paths can only be longer).

Implementation (Priority Queue)

int[] dijkstra(int source, int V, List<int[]>[] adj) {
    // adj[u] contains int[] {v, weight} for each edge u→v
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    // Min-heap: {distance, node}
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, source});

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], node = curr[1];

        if (d > dist[node]) continue;  // stale entry — already found a shorter path

        for (int[] edge : adj[node]) {
            int neighbor = edge[0], weight = edge[1];
            int newDist = dist[node] + weight;
            if (newDist < dist[neighbor]) {
                dist[neighbor] = newDist;
                pq.offer(new int[]{newDist, neighbor});
            }
        }
    }
    return dist;
}

Time: O((V + E) log V). Each node is added to the PQ at most once per incoming edge (O(E) total PQ insertions), each insertion/extraction is O(log V).

Space: O(V + E) for the graph and O(V) for dist[].

The Stale Entry Pattern

Java’s PriorityQueue doesn’t support decrease-key efficiently. Instead, we allow a node to be in the PQ multiple times with different distances, and discard stale entries with if (d > dist[node]) continue. This is standard practice on LeetCode.

What most people get wrong: using Dijkstra on a graph with negative edge weights. The greedy assumption — “if we settle a node, its distance is final” — breaks when a negative edge could create a shorter path to an already-settled node. On a graph with negative edges, Dijkstra can return incorrect results without erroring out. The failure is silent.

Bellman-Ford

Bellman-Ford solves single-source shortest paths even in the presence of negative edge weights. It also detects negative weight cycles — cycles where the total weight is negative, meaning “shortest path” is undefined because you can keep looping to reduce cost indefinitely.

Core idea: relax all edges V-1 times. Why V-1? The shortest path between any two vertices in a graph with no negative cycles can contain at most V-1 edges (a simple path visits at most V vertices). So V-1 iterations of relaxing all edges guarantees all shortest paths are found.

After V-1 iterations, perform one more pass: if any edge can still be relaxed, a negative cycle exists.

Implementation

int[] bellmanFord(int source, int V, int[][] edges) {
    // edges[i] = {u, v, weight}
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    // Relax all edges V-1 times
    for (int i = 0; i < V - 1; i++) {
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // Check for negative cycles: if any edge still relaxes, cycle exists
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
            System.out.println("Negative cycle detected");
            return null;
        }
    }

    return dist;
}

Time: O(V × E). This is considerably slower than Dijkstra. Space: O(V) for dist[].

Bellman-Ford for K-Hop Paths (LC 787)

A variant: “cheapest flight with at most K stops.” You need shortest path that uses at most K+1 edges. Run Bellman-Ford for exactly K+1 iterations, and copy the dist array before each iteration to prevent “chaining” — using the result of a relaxation from the same iteration as input for another relaxation in the same iteration.

int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    for (int i = 0; i <= k; i++) {           // k stops = k+1 edges
        int[] temp = dist.clone();            // copy BEFORE this iteration
        for (int[] flight : flights) {
            int u = flight[0], v = flight[1], w = flight[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < temp[v]) {
                temp[v] = dist[u] + w;
            }
        }
        dist = temp;
    }

    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

The dist.clone() before the inner loop is the critical detail. Without it, a single iteration might chain multiple hops — updating dist[v] using a dist[u] that was itself updated earlier in the same iteration.

Floyd-Warshall

Floyd-Warshall computes all-pairs shortest paths — the shortest path between every pair of vertices. It works on graphs with negative edges (but not negative cycles).

Core idea: the DP formulation. dp[i][j][k] = shortest path from i to j using only vertices 0..k as intermediate nodes. The recurrence:

dp[i][j][k] = min(dp[i][j][k-1],  dp[i][k][k-1] + dp[k][j][k-1])
                 (don't use k)        (go through k)

Since dp[i][j][k] only depends on dp[i][j][k-1], the outer dimension can be eliminated — just use a 2D matrix and iterate k in the outermost loop.

Implementation

int[][] floydWarshall(int V, int[][] dist) {
    // dist[i][j] = initial weight of edge i→j
    // dist[i][j] = INF if no direct edge
    // dist[i][i] = 0

    for (int k = 0; k < V; k++) {          // k = intermediate vertex (MUST be outer)
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // After: dist[i][j] = shortest path from i to j
    // Check for negative cycles: if dist[i][i] < 0, there's a negative cycle through i
    return dist;
}

Time: O(V³). Use only when V is small (≤ 500 for most systems). Space: O(V²).

What most people get wrong: putting the intermediate vertex k in the inner loop instead of the outer loop. The correctness of Floyd-Warshall depends on the order: when you compute dist[i][j] using intermediate vertex k, you need the optimal distances through all intermediates 0..k-1 to already be in the table. With k in the inner loop, this invariant is violated.

0-1 BFS (Revisited in Shortest Path Context)

Covered in the BFS/DFS file, but worth framing here: 0-1 BFS solves shortest paths when edge weights are exactly 0 or 1. Use a deque: weight-0 edges push to front (same cost level), weight-1 edges push to back.

Time: O(V + E), which beats Dijkstra’s O((V+E) log V) for this special case.

Algorithm Selection Table

Situation

Algorithm

Complexity

Unweighted graph, shortest hop count

BFS

O(V + E)

Non-negative weights, single source

Dijkstra

O((V+E) log V)

Negative weights OR negative cycle detection

Bellman-Ford

O(V × E)

All-pairs shortest paths

Floyd-Warshall

O(V³)

Edge weights 0 or 1 only

0-1 BFS

O(V + E)

Shortest path, at most K hops

Bellman-Ford (K iterations)

O(K × E)

Practice Problems

#

Problem

Difficulty

Algorithm

1

LC 743 — Network Delay Time

Medium

Dijkstra (directed, positive weights)

2

LC 1514 — Path With Maximum Probability

Medium

Dijkstra (max-heap variant)

3

LC 787 — Cheapest Flights Within K Stops

Medium

Bellman-Ford (K iterations)

4

LC 1334 — Find the City with Smallest Number of Neighbors

Medium

Floyd-Warshall

5

LC 1368 — Minimum Cost to Make Array Equal

Medium

0-1 BFS

6

LC 1631 — Path with Minimum Effort

Medium

Dijkstra (min of max edge weight)

For problem 2 (Maximum Probability): Dijkstra works for maximization too — just invert: use a max-heap instead of min-heap, and multiply probabilities instead of summing weights. The greedy invariant holds: when you process a node, its probability is maximal.

Problem 6 (Minimum Effort): the “weight” is the maximum absolute difference along the path. This is a minimax path problem. Dijkstra works if you define dist[node] as “minimum possible maximum difference to reach node” and relax accordingly.