Graph Shortest Paths: Dijkstra and Bellman-Ford

algorithm selection for Single-Source Shortest Path (SSSP)

Dijkstra's Algorithm

Core Logic: A greedy strategy combined with a Priority Queue (Min-Heap). Always extract the node with the smallest current distance from the source, then "relax" its outgoing edges to update neighbors' distances.

Prerequisite: All edge weights must be non-negative.

Network Delay Time (LeetCode 743)

Calculate the minimum time for all nodes to receive a signal from source k. This is the distance to the furthest reachable node.

int networkDelayTime(int[][] times, int n, int k) {
    // 1. Build adjacency list: node -> List<[neighbor, weight]>
    Map<Integer, List<int[]>> adjacency = new HashMap<>();
    for (int[] t : times) {
        adjacency.computeIfAbsent(t[0], key -> new ArrayList<>()).add(new int[]{t[1], t[2]});
    }

    // 2. Initialize distances
    int[] minDistance = new int[n + 1];
    Arrays.fill(minDistance, Integer.MAX_VALUE);
    minDistance[k] = 0;

    // 3. Min-Heap: [cumulativeDistance, targetNode]
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, k});

    while (!pq.isEmpty()) {
        int[] current = pq.poll();
        int d = current[0], u = current[1];
        
        // Optimization: if we already found a shorter path to 'u', discard this one
        if (d > minDistance[u]) continue;

        for (int[] edge : adjacency.getOrDefault(u, new ArrayList<>())) {
            int v = edge[0], weight = edge[1];
            // Relaxation step
            if (minDistance[u] + weight < minDistance[v]) {
                minDistance[v] = minDistance[u] + weight;
                pq.offer(new int[]{minDistance[v], v});
            }
        }
    }

    // 4. Result is the maximum value in minDistance array
    int maxDelay = 0;
    for (int i = 1; i <= n; i++) {
        if (minDistance[i] == Integer.MAX_VALUE) return -1;
        maxDelay = Math.max(maxDelay, minDistance[i]);
    }
    return maxDelay;
}

Path with Minimum Effort (LeetCode 1631)

This is a Dijkstra variant. Instead of path sum, we minimize the maximum difference between adjacent nodes on a path.

int minimumEffortPath(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    int[][] minEffort = new int[m][n];
    for (int[] row : minEffort) Arrays.fill(row, Integer.MAX_VALUE);
    minEffort[0][0] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, 0, 0}); // [effort, r, c]
    int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};

    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int e = top[0], r = top[1], c = top[2];
        
        if (r == m - 1 && c == n - 1) return e; 
        if (e > minEffort[r][c]) continue;

        for (int[] d : directions) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            
            // Local effort is max of current path's effort and adjacent diff
            int newEffort = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c]));
            if (newEffort < minEffort[nr][nc]) {
                minEffort[nr][nc] = newEffort;
                pq.offer(new int[]{newEffort, nr, nc});
            }
        }
    }
    return 0;
}

Shortest Path via Dynamic Programming (on DAGs)

Minimum Path Sum (LeetCode 64)

Since the matrix only allows moves down or right, it's a Directed Acyclic Graph (DAG). We can use pure DP.

int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    dp[0][0] = grid[0][0];

    // Initialize first column and row
    for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

Cheapest Flights Within K Stops (LeetCode 787)

This is a variant of Bellman-Ford, where we restrict the number of edge relaxations to exactly $K+1$.

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

    // Relax all edges up to k+1 times
    for (int i = 0; i <= k; i++) {
        int[] tempCosts = Arrays.copyOf(costs, n);
        for (int[] flight : flights) {
            int u = flight[0], v = flight[1], price = flight[2];
            if (costs[u] == Integer.MAX_VALUE) continue;
            
            if (costs[u] + price < tempCosts[v]) {
                tempCosts[v] = costs[u] + price;
            }
        }
        costs = tempCosts; // Crucial: swap to only use values from previous round
    }
    return costs[dst] == Integer.MAX_VALUE ? -1 : costs[dst];
}

Why the tempCosts array? Without it, you might calculate a path with more than 1 edge in a single iteration (cascading updates), violating the "within K stops" constraint.

Summary Selection Table