最短路径算法为何如此重要从Dijkstra到Floyd的四种实现方式与LeetCode完整通关指南

1956年的某个早晨，荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）在阿姆斯特丹的一家咖啡馆里，只用20分钟就在脑海中设计出了最短路径算法。当时他正在和未婚妻逛街，甚至没有用纸笔——这个"20分钟的发明"后来成为计算机科学史上最著名的算法之一，被广泛应用于GPS导航、网络路由、社交网络分析等无数领域。

最短路径问题是图论中最基础也最重要的问题之一。给定一个带权图，找出两个节点之间边权和最小的路径。这个问题看似简单，却催生了多种截然不同的算法，每种算法都有其独特的适用场景和权衡取舍。

问题的本质：为什么需要不同的算法

最短路径问题可以根据需求分为三类：

单源最短路径（Single-Source Shortest Path）：给定一个源点，求该点到图中所有其他点的最短路径。这是最常见的场景，比如导航系统中从当前位置到所有目的地的距离计算。

单对最短路径（Single-Pair Shortest Path）：只需要求两个特定点之间的最短路径。理论上这比单源问题更简单，但目前已知的最坏情况复杂度与单源问题相同。

多源最短路径（All-Pairs Shortest Path）：求图中任意两点之间的最短路径。这在需要频繁查询不同点对距离的场景中使用，比如城市间的航线距离矩阵。

更关键的是，图的特性会显著影响算法的选择：

边的权重：如果图中存在负权边，Dijkstra算法会失效
负权环：如果存在负权环，最短路径可能不存在（可以无限减小）
图的密度：稀疏图和稠密图适用的数据结构不同

这些因素共同决定了不存在一个"万能"的最短路径算法，我们需要根据具体情况选择合适的工具。

Dijkstra算法：贪心策略的优雅典范

Dijkstra算法的核心思想可以用一句话概括：始终选择当前距离源点最近的未访问节点。这是一个典型的贪心策略——每次做出局部最优选择，最终得到全局最优解。

算法流程

初始化距离数组，源点距离为0，其余为无穷大
将源点加入优先队列
从队列中取出距离最小的节点u
对于u的每个邻居v，如果通过u到达v的距离更短，则更新v的距离
将更新后的邻居加入队列
重复步骤3-5直到队列为空

这个流程的关键在于：一旦一个节点从队列中取出（即被"访问"），它的最短距离就已经确定了。这是因为我们总是优先处理距离最小的节点，任何后续发现的路径都不可能更短。

为什么不能处理负权边

考虑一个简单的反例：三个节点A、B、C，边权为 A→B = 1，A→C = 4，B→C = -3。

Dijkstra算法会先处理B（距离为1），然后处理C（距离为4）。当C被访问后，算法认为找到了A到C的最短路径是4。但实际上，A→B→C的路径长度是1 + (-3) = -2，比4更短。

这个问题的根源在于贪心策略的假设：当前最优一定是全局最优。负权边破坏了这个假设——即使一个节点已经被访问，后续仍可能通过负权边找到更短的路径。

时间复杂度分析

Dijkstra算法的时间复杂度取决于优先队列的实现：

数据结构	时间复杂度
数组	$O(V^2)$
二叉堆	$O((V+E)\log V)$
斐波那契堆	$O(E + V\log V)$

对于稀疏图（$E \approx V$），使用二叉堆的版本最优；对于稠密图（$E \approx V^2$），简单的数组版本反而更快，因为常系数更小。

Java实现

public class Dijkstra {
    public int[] shortestPath(int n, int[][] edges, int src) {
        // 构建邻接表
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        
        // 初始化距离数组
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        // 优先队列：[距离, 节点]
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, src});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];
            
            // 如果当前距离已不是最优，跳过
            if (d > dist[u]) continue;
            
            for (int[] neighbor : graph.get(u)) {
                int v = neighbor[0], w = neighbor[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        
        return dist;
    }
}

注意代码中的 if (d > dist[u]) continue; 这一行。这是处理优先队列中"过期"条目的技巧——同一个节点可能被多次加入队列，但我们只需要处理距离最小的那次。

Bellman-Ford：用松弛操作征服负权边

Bellman-Ford算法采用了一种完全不同的思路：暴力松弛。不依赖贪心选择，而是通过多轮迭代逐步逼近最优解。

松弛操作

松弛（Relaxation）是理解Bellman-Ford的关键。对于边 $(u, v)$，松弛操作定义为：

$$\text{if } dist[u] + w(u,v) < dist[v] \text{ then } dist[v] = dist[u] + w(u,v)$$

直观理解：如果通过u到达v比当前已知的路径更短，就更新v的距离。

为什么需要V-1轮迭代

考虑一条包含V个节点的最短路径。这条路径最多有V-1条边。Bellman-Ford每轮迭代对所有边进行松弛，第i轮迭代结束后，可以确定最多经过i条边的最短路径。因此，V-1轮迭代足以找到任意最短路径。

负权环检测

如果在V-1轮迭代后，仍然存在可以松弛的边，说明图中存在负权环。因为正常的最短路径最多V-1条边，如果V-1轮后还能优化，说明存在可以无限循环的负权路径。

public class BellmanFord {
    public int[] shortestPath(int n, int[][] edges, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        // V-1轮松弛
        for (int i = 0; i < n - 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;
                }
            }
        }
        
        // 检测负权环
        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]) {
                // 存在负权环
                return null;
            }
        }
        
        return dist;
    }
}

时间复杂度

Bellman-Ford的时间复杂度为 $O(VE)$，比Dijkstra的 $O(E\log V)$ 慢得多。但它的优势在于能处理负权边，这在某些实际场景中至关重要。

一个经典的应用是货币套利检测。将货币汇率取负对数作为边权，如果存在负权环，就意味着可以通过货币兑换获得无风险利润。

SPFA：Bellman-Ford的队列优化

SPFA（Shortest Path Faster Algorithm）是Bellman-Ford的一个重要优化。观察Bellman-Ford的过程，每轮迭代都对所有边进行松弛，但实际上很多松弛操作是无效的——只有当某个节点的距离被更新后，它的邻居才可能需要更新。

SPFA使用队列维护"距离发生变化的节点"，只对这些节点的出边进行松弛：

public class SPFA {
    public int[] shortestPath(int n, int[][] edges, int src) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        Queue<Integer> queue = new LinkedList<>();
        boolean[] inQueue = new boolean[n];
        queue.offer(src);
        inQueue[src] = true;
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;
            
            for (int[] neighbor : graph.get(u)) {
                int v = neighbor[0], w = neighbor[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    if (!inQueue[v]) {
                        queue.offer(v);
                        inQueue[v] = true;
                    }
                }
            }
        }
        
        return dist;
    }
}

SPFA的平均时间复杂度为 $O(E)$，最坏情况仍为 $O(VE)$。在随机图上表现优异，但刻意构造的数据可能导致性能退化。

Floyd-Warshall：动态规划的多源解决方案

Floyd-Warshall算法解决的是多源最短路径问题——求任意两点之间的最短路径。它采用了动态规划的思想，状态定义非常巧妙。

状态定义

设 $dp[k][i][j]$ 表示"只经过节点 $0, 1, ..., k$ 作为中间节点时，从i到j的最短路径长度"。

状态转移方程：

$$dp[k][i][j] = \min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])$$

含义：要么不经过节点k，最短路径就是 $dp[k-1][i][j]$；要么经过节点k，路径分成两段 $i \to k$ 和 $k \to j$。

空间优化

注意到 $dp[k]$ 只依赖于 $dp[k-1]$，可以用滚动数组优化空间：

public class FloydWarshall {
    public int[][] allPairsShortestPath(int n, int[][] edges) {
        int[][] dist = new int[n][n];
        
        // 初始化
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE / 2);
            dist[i][i] = 0;
        }
        for (int[] edge : edges) {
            dist[edge[0]][edge[1]] = edge[2];
        }
        
        // 动态规划
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        return dist;
    }
}

时间复杂度

Floyd-Warshall的时间复杂度为 $O(V^3)$，空间复杂度为 $O(V^2)$。虽然看起来很慢，但对于需要频繁查询任意两点距离的场景，这是一次性预处理，后续查询只需 $O(1)$。

算法选择指南

场景	推荐算法	时间复杂度
单源、非负权、稀疏图	Dijkstra + 二叉堆	$O((V+E)\log V)$
单源、非负权、稠密图	Dijkstra + 数组	$O(V^2)$
单源、存在负权边	Bellman-Ford / SPFA	$O(VE)$ / 平均 $O(E)$
检测负权环	Bellman-Ford	$O(VE)$
多源最短路径	Floyd-Warshall	$O(V^3)$
有边数限制的最短路	Bellman-Ford	$O(KE)$

LeetCode经典题目详解

LeetCode 743. Network Delay Time

题目：有n个网络节点，从节点k发出信号，求所有节点收到信号的最短时间。

分析：这是典型的单源最短路径问题。信号从k出发传播到所有节点，所需时间就是k到最远节点的最短路径长度。直接使用Dijkstra算法即可。

public int networkDelayTime(int[][] times, int n, int k) {
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i <= n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] time : times) {
        graph.get(time[0]).add(new int[]{time[1], time[2]});
    }
    
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, k});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
        if (d > dist[u]) continue;
        
        for (int[] neighbor : graph.get(u)) {
            int v = neighbor[0], w = neighbor[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 787. Cheapest Flights Within K Stops

题目：求从src到dst最多经过k个中转站的最便宜机票价格。

分析：这题有一个额外的约束——最多k个中转站。这限制了路径的边数不能超过k+1条。标准的Dijkstra算法不适用，因为它可能选择边数更少的次优路径。

Bellman-Ford算法天然适合这类问题：第i轮迭代后，找到的是最多经过i条边的最短路径。我们只需要运行k+1轮迭代。

public 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;
    
    // 最多k个中转站 = 最多k+1条边
    for (int i = 0; i <= k; i++) {
        int[] temp = dist.clone();
        for (int[] flight : flights) {
            int from = flight[0], to = flight[1], price = flight[2];
            if (dist[from] != Integer.MAX_VALUE && dist[from] + price < temp[to]) {
                temp[to] = dist[from] + price;
            }
        }
        dist = temp;
    }
    
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

这里使用 temp 数组保存本轮更新的结果，避免在同一轮迭代中使用刚更新的值，确保每轮迭代只增加一条边。

LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

题目：找到在距离阈值内可达城市数量最少的城市，如果有多个则返回编号最大的。

分析：这是多源最短路径问题，需要知道任意两个城市之间的最短距离。使用Floyd-Warshall算法计算所有点对的最短路径，然后统计每个城市在阈值内的可达城市数。

public int findTheCity(int n, int[][] edges, int distanceThreshold) {
    int[][] dist = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], Integer.MAX_VALUE / 2);
        dist[i][i] = 0;
    }
    for (int[] edge : edges) {
        dist[edge[0]][edge[1]] = edge[2];
        dist[edge[1]][edge[0]] = edge[2];
    }
    
    // Floyd-Warshall
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    int minCities = n, result = 0;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (i != j && dist[i][j] <= distanceThreshold) {
                count++;
            }
        }
        if (count <= minCities) {
            minCities = count;
            result = i;
        }
    }
    return result;
}

LeetCode 1514. Path with Maximum Probability

题目：求从start到end成功概率最大的路径。

分析：概率是相乘关系，而最短路径算法处理的是相加关系。通过对概率取负对数，可以将最大化概率问题转化为最小化距离问题。但更简单的做法是直接修改Dijkstra算法——将"最短"改为"最长"，将"松弛"改为"概率相乘"。

public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
    List<List<double[]>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int i = 0; i < edges.length; i++) {
        graph.get(edges[i][0]).add(new double[]{edges[i][1], succProb[i]});
        graph.get(edges[i][1]).add(new double[]{edges[i][0], succProb[i]});
    }
    
    double[] prob = new double[n];
    prob[start] = 1.0;
    
    // 最大堆
    PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));
    pq.offer(new double[]{1.0, start});
    
    while (!pq.isEmpty()) {
        double[] curr = pq.poll();
        double p = curr[0];
        int u = (int) curr[1];
        
        if (p < prob[u]) continue;
        if (u == end) return p;
        
        for (double[] neighbor : graph.get(u)) {
            int v = (int) neighbor[0];
            double edgeProb = neighbor[1];
            if (prob[u] * edgeProb > prob[v]) {
                prob[v] = prob[u] * edgeProb;
                pq.offer(new double[]{prob[v], v});
            }
        }
    }
    
    return 0.0;
}

这里使用最大堆代替最小堆，因为我们要求的是最大概率路径。

LeetCode 1631. Path With Minimum Effort

题目：找到一条从左上到右下的路径，使得路径上相邻格子高度差的最大值最小。

分析：这是一个"最小化最大值"问题。可以理解为：路径的"代价"不是边权之和，而是边权的最大值。这仍然可以用Dijkstra框架解决——将距离更新改为 dist[v] = max(dist[u], weight(u,v))。

public 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;
    
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, 0, 0});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int e = curr[0], r = curr[1], c = curr[2];
        
        if (r == m - 1 && c == n - 1) return e;
        if (e > effort[r][c]) continue;
        
        for (int[] dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                int newEffort = Math.max(e, Math.abs(heights[r][c] - heights[nr][nc]));
                if (newEffort < effort[nr][nc]) {
                    effort[nr][nc] = newEffort;
                    pq.offer(new int[]{newEffort, nr, nc});
                }
            }
        }
    }
    return 0;
}

LeetCode 399. Evaluate Division

题目：给定一系列除法等式，求未知除法的值。

分析：将变量看作节点，除法关系看作有向边。a / b = 2.0 表示 a → b 的边权为2.0，b → a 的边权为0.5。查询 a / c 就是找从a到c的路径，将路径上的边权相乘。

这可以用Floyd-Warshall解决，预先计算所有点对的结果：

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    Map<String, Integer> id = new HashMap<>();
    int nodeCount = 0;
    for (List<String> eq : equations) {
        if (!id.containsKey(eq.get(0))) id.put(eq.get(0), nodeCount++);
        if (!id.containsKey(eq.get(1))) id.put(eq.get(1), nodeCount++);
    }
    
    double[][] dist = new double[nodeCount][nodeCount];
    for (int i = 0; i < nodeCount; i++) {
        Arrays.fill(dist[i], -1.0);
        dist[i][i] = 1.0;
    }
    
    for (int i = 0; i < equations.size(); i++) {
        int u = id.get(equations.get(i).get(0));
        int v = id.get(equations.get(i).get(1));
        dist[u][v] = values[i];
        dist[v][u] = 1.0 / values[i];
    }
    
    // Floyd-Warshall
    for (int k = 0; k < nodeCount; k++) {
        for (int i = 0; i < nodeCount; i++) {
            for (int j = 0; j < nodeCount; j++) {
                if (dist[i][k] > 0 && dist[k][j] > 0) {
                    dist[i][j] = dist[i][k] * dist[k][j];
                }
            }
        }
    }
    
    double[] result = new double[queries.size()];
    for (int i = 0; i < queries.size(); i++) {
        String a = queries.get(i).get(0), b = queries.get(i).get(1);
        if (!id.containsKey(a) || !id.containsKey(b)) {
            result[i] = -1.0;
        } else {
            result[i] = dist[id.get(a)][id.get(b)];
        }
    }
    return result;
}

LeetCode 778. Swim in Rising Water

题目：在一个网格中，水位随时间上涨，求能从左上角游到右下角的最小时间。

分析：这题的本质和Path With Minimum Effort类似——路径的代价是经过的格子的最大高度。时间t时刻可以游过高度不超过t的格子，所以最小时间等于路径上最大高度的最小值。

public int swimInWater(int[][] grid) {
    int n = grid.length;
    int[][] time = new int[n][n];
    for (int[] row : time) Arrays.fill(row, Integer.MAX_VALUE);
    time[0][0] = grid[0][0];
    
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{grid[0][0], 0, 0});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int t = curr[0], r = curr[1], c = curr[2];
        
        if (r == n - 1 && c == n - 1) return t;
        if (t > time[r][c]) continue;
        
        for (int[] dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                int newTime = Math.max(t, grid[nr][nc]);
                if (newTime < time[nr][nc]) {
                    time[nr][nc] = newTime;
                    pq.offer(new int[]{newTime, nr, nc});
                }
            }
        }
    }
    return 0;
}

LeetCode 882. Reachable Nodes In Subdivided Graph

题目：每条边被细分为多个节点，求从节点0出发，最多移动maxMoves步能到达多少个节点。

分析：首先计算从节点0到每个原始节点的最短距离。如果最短距离不超过maxMoves，这个节点可以被到达。对于每条边，计算从两端出发各能覆盖多少中间节点。

public int reachableNodes(int[][] edges, int maxMoves, int n) {
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] edge : edges) {
        graph.get(edge[0]).add(new int[]{edge[1], edge[2] + 1});
        graph.get(edge[1]).add(new int[]{edge[0], edge[2] + 1});
    }
    
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[0] = 0;
    
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, 0});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
        if (d > dist[u]) continue;
        
        for (int[] neighbor : graph.get(u)) {
            int v = neighbor[0], w = neighbor[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    
    int result = 0;
    // 统计可达的原始节点
    for (int i = 0; i < n; i++) {
        if (dist[i] <= maxMoves) result++;
    }
    
    // 统计边上可达的中间节点
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], cnt = edge[2];
        int fromU = Math.max(0, maxMoves - dist[u]);
        int fromV = Math.max(0, maxMoves - dist[v]);
        result += Math.min(cnt, fromU + fromV);
    }
    
    return result;
}

LeetCode 1976. Number of Ways to Arrive at Destination

题目：求从节点0到节点n-1的最短路径的条数。

分析：在Dijkstra的基础上，额外维护一个计数数组。当发现更短路径时重置计数，当发现等长路径时累加计数。

public int countPaths(int n, int[][] roads) {
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] road : roads) {
        graph.get(road[0]).add(new int[]{road[1], road[2]});
        graph.get(road[1]).add(new int[]{road[0], road[2]});
    }
    
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[0] = 0;
    
    long[] ways = new long[n];
    ways[0] = 1;
    
    int MOD = 1_000_000_007;
    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    pq.offer(new long[]{0, 0});
    
    while (!pq.isEmpty()) {
        long[] curr = pq.poll();
        long d = curr[0];
        int u = (int) curr[1];
        
        if (d > dist[u]) continue;
        
        for (int[] neighbor : graph.get(u)) {
            int v = neighbor[0], w = neighbor[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                ways[v] = ways[u];
                pq.offer(new long[]{dist[v], v});
            } else if (dist[u] + w == dist[v]) {
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    
    return (int) ways[n - 1];
}

LeetCode 2045. Second Minimum Time to Reach Destination

题目：求从节点1到节点n的严格第二短时间。

分析：不仅需要最短距离，还需要严格第二短的距离。可以维护两个距离数组：最短和次短。当发现更短路径时更新最短，原来的最短变成次短；当发现介于最短和次短之间的路径时更新次短。

public int secondMinimum(int n, int[][] edges, int time, int change) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    }
    
    int[] dist1 = new int[n + 1];
    int[] dist2 = new int[n + 1];
    Arrays.fill(dist1, Integer.MAX_VALUE);
    Arrays.fill(dist2, Integer.MAX_VALUE);
    dist1[1] = 0;
    
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{1, 0});
    
    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int u = curr[0], d = curr[1];
        
        for (int v : graph.get(u)) {
            if (d + 1 < dist1[v]) {
                dist2[v] = dist1[v];
                dist1[v] = d + 1;
                queue.offer(new int[]{v, d + 1});
            } else if (d + 1 > dist1[v] && d + 1 < dist2[v]) {
                dist2[v] = d + 1;
                queue.offer(new int[]{v, d + 1});
            }
        }
    }
    
    // 计算实际时间
    int steps = dist2[n];
    int totalTime = 0;
    for (int i = 0; i < steps; i++) {
        // 等红灯
        if ((totalTime / change) % 2 == 1) {
            totalTime = ((totalTime / change) + 1) * change;
        }
        totalTime += time;
    }
    
    return totalTime;
}

LeetCode 2642. Design Graph With Shortest Path Calculator

题目：设计一个支持动态添加边和查询最短路径的数据结构。

分析：这是一个图数据结构设计题。如果图是静态的，Floyd-Warshall可以支持O(1)查询。但对于动态添加边的情况，需要权衡更新代价和查询代价。一种折中方案是每次查询时运行Dijkstra。

class Graph {
    private List<List<int[]>> graph;
    private int n;
    
    public Graph(int n, int[][] edges) {
        this.n = n;
        this.graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            addEdge(edge);
        }
    }
    
    public void addEdge(int[] edge) {
        graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
    }
    
    public int shortestPath(int node1, int node2) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[node1] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, node1});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];
            if (u == node2) return d;
            if (d > dist[u]) continue;
            
            for (int[] neighbor : graph.get(u)) {
                int v = neighbor[0], w = neighbor[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        
        return -1;
    }
}

总结

最短路径算法家族展示了算法设计中的几个核心思想：

贪心策略的威力：Dijkstra算法证明了在特定条件下（非负权），局部最优选择可以导向全局最优。这是贪心算法成功的经典案例。

松弛操作的普适性：Bellman-Ford和SPFA都基于松弛操作，展示了如何通过反复改进逐步逼近最优解。这种迭代改进的思想在许多优化算法中都有应用。

动态规划的状态设计：Floyd-Warshall巧妙地引入"中间节点编号上限"作为状态维度，将多源最短路径问题转化为经典的DP问题。

算法选择的权衡：没有一种算法在所有场景下都最优。Dijkstra快但不能处理负权，Bellman-Ford通用但慢，Floyd-Warshall适合多源查询但空间消耗大。理解每种算法的适用边界，比记住具体实现更重要。

参考资料

Dijkstra, E. W. (1959). “A note on two problems in connexion with graphs”. Numerische Mathematik. 1: 269–271.
Bellman, R. (1958). “On a routing problem”. Quarterly of Applied Mathematics. 16: 87–90.
Floyd, R. W. (1962). “Algorithm 97: Shortest path”. Communications of the ACM. 5 (6): 345.
Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
OI Wiki - 最短路
LeetCode Graph Problems Discussion

问题的本质：为什么需要不同的算法#

Dijkstra算法：贪心策略的优雅典范#

算法流程#

为什么不能处理负权边#

时间复杂度分析#

Java实现#

Bellman-Ford：用松弛操作征服负权边#

松弛操作#

为什么需要V-1轮迭代#

负权环检测#

时间复杂度#

SPFA：Bellman-Ford的队列优化#

Floyd-Warshall：动态规划的多源解决方案#

状态定义#

空间优化#

时间复杂度#

算法选择指南#

LeetCode经典题目详解#

LeetCode 743. Network Delay Time#

LeetCode 787. Cheapest Flights Within K Stops#

LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance#

LeetCode 1514. Path with Maximum Probability#

LeetCode 1631. Path With Minimum Effort#

LeetCode 399. Evaluate Division#

LeetCode 778. Swim in Rising Water#

LeetCode 882. Reachable Nodes In Subdivided Graph#

LeetCode 1976. Number of Ways to Arrive at Destination#

LeetCode 2045. Second Minimum Time to Reach Destination#

LeetCode 2642. Design Graph With Shortest Path Calculator#

总结#

参考资料#

更多精彩内容

拓扑排序如何让任务有条不紊地执行：从Kahn算法到DFS的完整LeetCode通关指南

股票买卖问题为何能用一套代码解决所有变体从状态机DP到贪心的统一框架

状态压缩动态规划为何能用一个整数表示整个集合从旅行商问题到LeetCode完整通关指南

区间动态规划为何要按长度递增遍历从矩阵链乘法到戳气球的完整LeetCode通关指南

Tarjan算法为何能用一次DFS完成图论四大难题从强连通分量到桥与割点的完整LeetCode通关指南

问题的本质：为什么需要不同的算法

Dijkstra算法：贪心策略的优雅典范

算法流程

为什么不能处理负权边

时间复杂度分析

Java实现

Bellman-Ford：用松弛操作征服负权边

松弛操作

为什么需要V-1轮迭代

负权环检测

时间复杂度

SPFA：Bellman-Ford的队列优化

Floyd-Warshall：动态规划的多源解决方案

状态定义

空间优化

时间复杂度

算法选择指南

LeetCode经典题目详解

LeetCode 743. Network Delay Time

LeetCode 787. Cheapest Flights Within K Stops

LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

LeetCode 1514. Path with Maximum Probability

LeetCode 1631. Path With Minimum Effort

LeetCode 399. Evaluate Division

LeetCode 778. Swim in Rising Water

LeetCode 882. Reachable Nodes In Subdivided Graph

LeetCode 1976. Number of Ways to Arrive at Destination

LeetCode 2045. Second Minimum Time to Reach Destination

LeetCode 2642. Design Graph With Shortest Path Calculator

总结

参考资料