跳到主要内容

图的最短路径

最短路径问题是指在图中寻找两个顶点之间"代价"最小的路径。这里的"代价"可以是距离、时间、费用等，通常用边上的权重表示。最短路径问题是图论中最重要的问题之一，在导航系统、网络路由、物流规划等领域有广泛应用。

问题分类​

最短路径问题可以根据不同的维度进行分类：

按源点数量：

  • 单源最短路径：求一个源点到所有其他顶点的最短路径
  • 多源最短路径：求任意两个顶点之间的最短路径

按边权特性：

  • 无权图：每条边权重相同（可视为权重为1）
  • 正权图：所有边权重为正数
  • 含负权边：存在权重为负的边
  • 含负环：存在总权重为负的环

不同的问题类型需要不同的算法来解决。

无权图：BFS​

对于无权图（或所有边权重相同），BFS 天然就是最短路径算法。因为 BFS 按层级遍历，第一次到达某个顶点时经过的边数就是最短距离。

算法原理​

BFS 从源点开始，逐层向外扩展。每一层代表距离源点相同距离的所有顶点。因此，第一次访问某个顶点时，所经过的路径就是最短路径。

代码实现​

public int[] bfsShortestPath(List<List<Integer>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, -1);  // -1 表示不可达
    
    Queue<Integer> queue = new LinkedList<>();
    dist[start] = 0;
    queue.offer(start);
    
    while (!queue.isEmpty()) {
        int u = queue.poll();
        
        for (int v : graph.get(u)) {
            if (dist[v] == -1) {  // 未访问过
                dist[v] = dist[u] + 1;
                queue.offer(v);
            }
        }
    }
    
    return dist;
}

时间复杂度：O(V+E)O(V + E) 空间复杂度：O(V)O(V)

单源最短路径：Dijkstra 算法​

Dijkstra 算法是解决非负权重图单源最短路径问题的经典算法，基于贪心思想。

算法原理​

Dijkstra 算法的核心思想是：每次选择距离源点最近的未确定顶点，确定其最短路径，然后更新其邻居的距离。

为什么贪心选择正确？

关键在于非负权重。当我们选择距离最小的顶点 uu 时，其他未确定顶点的距离都大于等于 dist[u]dist[u]。由于边权非负，通过其他顶点到达 uu 的距离只会更大，不可能更小。因此，dist[u]dist[u] 已经是最短距离。

算法步骤​

  1. 初始化：源点距离为 0，其他顶点距离为无穷大
  2. 从未确定顶点中选择距离最小的顶点 uu
  3. 标记 uu 为已确定
  4. 对 uu 的每个邻居 vv，尝试松弛：dist[v]=min⁡(dist[v],dist[u]+weight(u,v))dist[v] = \min(dist[v], dist[u] + weight(u,v))
  5. 重复步骤 2-4 直到所有顶点都确定

代码实现​

朴素实现（邻接矩阵）：

public int[] dijkstra(int[][] graph, int start) {
    int n = graph.length;
    int[] dist = new int[n];           // 最短距离
    boolean[] visited = new boolean[n]; // 是否已确定
    
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    
    for (int i = 0; i < n; i++) {
        // 找未确定顶点中距离最小的
        int u = -1;
        int minDist = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }
        
        if (u == -1) break;  // 剩余顶点不可达
        visited[u] = true;
        
        // 更新邻居距离
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != 0 && 
                dist[u] != Integer.MAX_VALUE && 
                dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    
    return dist;
}

优先队列优化（邻接表）：

public int[] dijkstra(List<List<int[]>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    
    // 优先队列：{顶点, 距离}，按距离排序
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{start, 0});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int u = curr[0], d = curr[1];
        
        // 可能存在冗余，如果当前距离大于已记录距离则跳过
        if (d > dist[u]) continue;
        
        // 遍历邻居：int[] {顶点, 权重}
        for (int[] edge : graph.get(u)) {
            int v = edge[0], w = edge[1];
            
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    
    return dist;
}

时间复杂度分析​

实现方式时间复杂度说明
邻接矩阵 + 朴素实现O(V2)O(V^2)每次找最小值需要 O(V)O(V)
邻接表 + 优先队列O((V+E)log⁡V)O((V+E) \log V)优先队列操作
斐波那契堆O(Vlog⁡V+E)O(V \log V + E)理论最优

实际选择：

  • 稠密图（E≈V2E \approx V^2）：朴素实现 O(V2)O(V^2) 更优
  • 稀疏图（E≈VE \approx V）：优先队列 O(Elog⁡V)O(E \log V) 更优

获取最短路径​

如果需要记录路径本身，可以维护一个前驱数组：

public int[] dijkstraWithPath(List<List<int[]>> graph, int start, int[] prev) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    Arrays.fill(prev, -1);  // 前驱初始化为 -1
    
    dist[start] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{start, 0});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int u = curr[0], d = curr[1];
        
        if (d > dist[u]) continue;
        
        for (int[] edge : graph.get(u)) {
            int v = edge[0], w = edge[1];
            
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                prev[v] = u;  // 记录前驱
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    
    return dist;
}

// 从终点回溯到起点获取路径
public List<Integer> reconstructPath(int[] prev, int end) {
    List<Integer> path = new ArrayList<>();
    for (int at = end; at != -1; at = prev[at]) {
        path.add(at);
    }
    Collections.reverse(path);
    return path;
}

Dijkstra 的局限​

Dijkstra 算法不能处理负权边。原因在于贪心选择的前提是非负权重：如果存在负权边，通过更远的顶点可能得到更短的路径，破坏了贪心的正确性。

含负权边：Bellman-Ford 算法​

Bellman-Ford 算法可以处理含负权边的图，并能检测负环。

算法原理​

Bellman-Ford 基于松弛操作：对于边 (u,v)(u, v)，如果 dist[u]+weight(u,v)<dist[v]dist[u] + weight(u, v) < dist[v]，则更新 dist[v]dist[v]。

关键观察：在一个有 VV 个顶点的图中，最短路径最多包含 V−1V-1 条边（否则会形成环，而正环不会出现在最短路径中）。因此，对所有边进行 V−1V-1 轮松弛，就能保证找到最短路径。

算法步骤​

  1. 初始化：源点距离为 0，其他顶点距离为无穷大
  2. 对所有边进行 V−1V-1 轮松弛操作
  3. （可选）第 VV 轮检测负环：如果还能松弛，说明存在负环

代码实现​

public int[] bellmanFord(int n, int[][] edges, int start) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 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]) {
            throw new IllegalArgumentException("图中存在负环");
        }
    }
    
    return dist;
}

时间复杂度​

时间复杂度：O(V⋅E)O(V \cdot E) 空间复杂度：O(V)O(V)

相比 Dijkstra 的 O(Elog⁡V)O(E \log V)，Bellman-Ford 更慢，但功能更强大。

为什么能检测负环？​

如果第 VV 轮松弛仍然能更新距离，说明存在一条路径，其边数超过 V−1V-1 条但还能缩短距离。这只有在存在负环时才可能，因为正环不会缩短距离。

应用场景​

  • 处理含负权边的图
  • 检测图中是否存在负环
  • 金融领域的套利检测（汇率转换中的负环意味着套利机会）

有向无环图（DAG）：拓扑排序​

对于有向无环图（DAG），可以利用拓扑排序在 O(V+E)O(V+E) 时间内求出单源最短路径。

算法原理​

DAG 的拓扑排序保证：对于每条边 (u,v)(u, v)，uu 在排序中位于 vv 之前。因此，按照拓扑序处理顶点，处理某个顶点时，所有能到达它的顶点都已经处理完毕。

代码实现​

public int[] shortestPathDAG(List<List<int[]>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    
    // 获取拓扑排序
    int[] topoOrder = topologicalSort(graph);
    
    // 按拓扑序处理
    for (int u : topoOrder) {
        if (dist[u] != Integer.MAX_VALUE) {
            for (int[] edge : graph.get(u)) {
                int v = edge[0], w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }
    
    return dist;
}

时间复杂度：O(V+E)O(V + E) 空间复杂度：O(V)O(V)

这是单源最短路径问题的最优解法，但仅适用于 DAG。

多源最短路径：Floyd-Warshall 算法​

Floyd-Warshall 算法求解所有顶点对之间的最短路径，基于动态规划思想。

算法原理​

定义 dist[k][i][j]dist[k][i][j] 表示从顶点 ii 到顶点 jj，只允许经过编号不超过 kk 的顶点作为中间点的最短路径。

状态转移： dist[k][i][j]=min⁡(dist[k−1][i][j],dist[k−1][i][k]+dist[k−1][k][j])dist[k][i][j] = \min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])

含义：要么不经过顶点 kk，要么经过顶点 kk。

由于 dist[k]dist[k] 只依赖 dist[k−1]dist[k-1]，可以优化为二维数组： dist[i][j]=min⁡(dist[i][j],dist[i][k]+dist[k][j])dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])

代码实现​

public int[][] floydWarshall(int[][] graph) {
    int n = graph.length;
    int[][] dist = new int[n][n];
    
    // 初始化距离矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                dist[i][j] = 0;
            } else if (graph[i][j] != 0) {
                dist[i][j] = graph[i][j];
            } else {
                dist[i][j] = Integer.MAX_VALUE / 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;
}

检测负环​

如果最终存在 dist[i][i]<0dist[i][i] < 0，说明存在经过顶点 ii 的负环。

public boolean hasNegativeCycle(int[][] dist) {
    for (int i = 0; i < dist.length; i++) {
        if (dist[i][i] < 0) {
            return true;
        }
    }
    return false;
}

时间复杂度​

时间复杂度：O(V3)O(V^3) 空间复杂度：O(V2)O(V^2)

虽然时间复杂度较高，但代码简洁，适合顶点数较少的情况。如果对每个顶点运行 Dijkstra，总时间为 O(V⋅Elog⁡V)O(V \cdot E \log V)，在稠密图（E≈V2E \approx V^2）时接近 O(V3log⁡V)O(V^3 \log V)，不如 Floyd-Warshall。

算法对比​

算法适用场景时间复杂度能否处理负权边
BFS无权图O(V+E)O(V+E)不适用
Dijkstra非负权图O(Elog⁡V)O(E \log V)否
Bellman-Ford含负权边O(V⋅E)O(V \cdot E)是
拓扑排序DAGO(V+E)O(V+E)是
Floyd-Warshall多源最短路径O(V3)O(V^3)是

选择建议​

  1. 无权图：直接用 BFS
  2. 非负权重、单源：Dijkstra（优先队列版本）
  3. 含负权边：Bellman-Ford
  4. DAG：拓扑排序 + 松弛
  5. 多源最短路径：
    • 顶点少（V<400V < 400）：Floyd-Warshall
    • 顶点多：对每个顶点运行 Dijkstra

经典应用​

网络延迟时间（LeetCode 743）​

有 n 个网络节点，给定边列表 times = (u, v, w) 表示信号从 u 传到 v 需要时间 w。求从节点 k 发出信号，所有节点收到信号的最短时间。

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[] t : times) {
        graph.get(t[0]).add(new int[]{t[1], t[2]});
    }
    
    // Dijkstra
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{k, 0});
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int u = curr[0], d = curr[1];
        
        if (d > dist[u]) continue;
        
        for (int[] edge : graph.get(u)) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    
    // 找最大延迟时间
    int maxDelay = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;  // 有节点不可达
        maxDelay = Math.max(maxDelay, dist[i]);
    }
    
    return maxDelay;
}

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

给定 flights 和最多中转 K 次，求从 src 到 dst 的最便宜价格。

这是一个限制边数的最短路径问题，可以用 Bellman-Ford 的变种解决：只进行 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+1 轮松弛（K 次中转 = K+1 条边）
    for (int i = 0; i <= k; i++) {
        int[] temp = dist.clone();  // 避免本轮更新影响本轮其他边
        
        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];
}

阈值距离内邻居最少的城市（LeetCode 1334）​

找出从某城市出发，在距离阈值内能到达的城市数最少的城市。

使用 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[] e : edges) {
        dist[e[0]][e[1]] = e[2];
        dist[e[1]][e[0]] = e[2];
    }
    
    // Floyd-Warshall
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    // 找邻居最少的城市
    int minNeighbors = n;
    int 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 <= minNeighbors) {
            minNeighbors = count;
            result = i;  // 编号大的优先，所以用 <=
        }
    }
    
    return result;
}

小结​

最短路径算法是图算法的核心内容：

核心要点：

  • BFS 适用于无权图
  • Dijkstra 适用于非负权重，贪心选择
  • Bellman-Ford 可处理负权边，能检测负环
  • Floyd-Warshall 求多源最短路径，动态规划

选择依据：

  • 权重特性（无权、正权、负权）
  • 问题类型（单源、多源）
  • 图的规模和稀疏程度

注意事项：

  • Dijkstra 不能处理负权边
  • Bellman-Ford 时间复杂度较高但功能全面
  • Floyd-Warshall 适合顶点数较少的情况

练习​

基础：

  1. LeetCode 743：网络延迟时间
  2. LeetCode 1514：概率最大的路径
  3. LeetCode 1334：阈值距离内邻居最少的城市

进阶： 4. LeetCode 787：K 站中转内最便宜的航班 5. LeetCode 1631：最小体力消耗路径 6. LeetCode 882：细分图中的可到达节点 7. LeetCode 2642：设计图最短路径类

挑战： 8. LeetCode 1334：用 Dijkstra 实现 9. 实现检测负环的 Bellman-Ford 10. 实现带路径重建的 Dijkstra