图的最短路径：Dijkstra 与 Bellman-Ford

单源最短路径算法选择

Dijkstra 算法

思路：贪心 + 优先级队列（小根堆）。每次从堆中取出当前距离最小的节点，更新其邻居的距离。

前提：边权非负（否则贪心不成立）。

网络延迟时间（LeetCode 743）

int networkDelayTime(int[][] times, int n, int k) {
    // 建邻接表
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int[] t : times) {
        graph.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});
    }

    // dist[i] = 从 k 到 i 的最短距离
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;

    // 小根堆：[distance, node]
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, k});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;  // 已找到更短路径，跳过

        for (int[] edge : graph.getOrDefault(u, new ArrayList<>())) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }

    int maxDist = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;
        maxDist = Math.max(maxDist, dist[i]);
    }
    return maxDist;
}

路径中的最小值（LeetCode 1631）

类 Dijkstra，将「距离最短」改为「路径上最大差值最小」：

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

    // [effort, row, col]
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, 0, 0});
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

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

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int newEffort = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c]));
            if (newEffort < effort[nr][nc]) {
                effort[nr][nc] = newEffort;
                pq.offer(new int[]{newEffort, nr, nc});
            }
        }
    }
    return 0;
}

动态规划求最短路（DAG 上）

最小路径和（LeetCode 64）

DAG（只能向右/向下走）上的最短路，直接 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];

    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];
}

K 站中转内最便宜的航班（LeetCode 787）

Bellman-Ford 变体：最多使用 k 条边的最短路，每轮松弛一次边：

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

    for (int i = 0; i <= k; i++) {  // k+1 轮松弛（最多 k 次中转）
        int[] tmp = Arrays.copyOf(prices, n);
        for (int[] f : flights) {
            int from = f[0], to = f[1], price = f[2];
            if (prices[from] == Integer.MAX_VALUE) continue;
            tmp[to] = Math.min(tmp[to], prices[from] + price);
        }
        prices = tmp;
    }
    return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
}

注意：每轮从上一轮的 prices 读，写入 tmp，防止同轮内传播（即「一步多跳」问题）。

关键区别汇总