图的最短路问题

MrHe··5 min read

聊到图论，最短路是个绕不开的坎。别看它名字简单，里面的门道可不少。不管是面试还是实际应用（比如地图导航、网络路由），这玩意儿都极其重要。

很多时候我们看到一个算法题，如果没有思路，第一反应是啥？暴力枚举呗。那最短路的暴力解法是啥？把从起点到终点的所有可能路径都列出来，然后一个个算它们的权重和，最后取个最小值。

想法很简单，但你稍微画个图就知道，一个稍微复杂点的图，路径的数量就是指数级爆炸，这谁顶得住？所以，暴力解法咱们心里有数就行了，它只能作为思考的起点，根本没法写。

今天，咱们就从正经的解法开始，一步步把最短路问题给办了。我会给你整明白三种在不同场景下称王称霸的经典算法：Dijkstra、Bellman-Ford 和 Floyd-Warshall。

解法一：Dijkstra 算法 - 没有负权重边的世界，我就是王

Dijkstra 算法可以说是最短路算法里最经典、最常用的了。但是它有个前提：图里不能有负权重边。这个前提非常重要，后面我会解释为什么。

它的核心思想其实是一种贪心策略。想象一下，你站在起点，想去图里的其他所有点。

  1. 最开始，你只知道起点到自己的距离是0，到其他所有点的距离都是无穷大（因为还没出发嘛）。

  2. 然后，你环顾四周，看看所有与你直接相连的点，选一个离你最近的，比如说点 A。好了，那起点到 A 的最短距离就被你确定了，因为任何更远的路径，都不可能比直接走过去更短了（记住，没有负权重边，所以不存在绕个远路反而能“减负”的情况）。

  3. 现在你把点 A “解锁”了。接下来，你就要利用点 A 这个新的据点。从 A 出发，看看它能走到哪些点 B、C、D...。然后更新起点经过 A 到达这些点的距离。比如起点到 C 的距离原来是无穷大，但现在发现可以“起点 -> A -> C”，那就有了一条新路径，你就把这个距离记录下来。如果发现“起点 -> A -> B”比之前记录的直达 B 的路径更短，那当然也更新一下。

  4. 重复这个过程：在所有还没“解锁”的点里，再选一个当前已知距离最小的点，解锁它，然后用它来更新它的邻居。

这个过程就像水波纹一样，从起点开始，一圈一圈地向外扩展，每次都锁定一个当前看起来最近的点，最终确定所有点的最短路径。

Dijkstra 的实现细节

最朴素的实现，每次都遍历所有未锁定的点来找那个距离最小的，效率比较低。咱们玩算法的，肯定要追求极致。这里要用一个神器：小根堆（PriorityQueue）。

小根堆能帮我们干啥？它能以 O(logN) 的代价，快速找到那个“当前已知距离最小”的点。

整个流程就变成了：

  1. 准备一个 distanceMap，记录起点到各个点的距离，初始时只有起点是0，其他都是无穷大。

  2. 准备一个小根堆，把起点放进去。

  3. 当堆不为空时，弹出堆顶元素（也就是当前已知距离最小的点，记为 cur）。

  4. 如果 cur 已经被处理过了，跳过（这是为了处理堆中可能存在的重复记录）。

  5. 遍历 cur 的所有邻居 next。计算从起点经过 cur 到达 next 的距离 newDist。

  6. 如果 newDist 比 distanceMap 中记录的到 next 的距离更短，就更新 distanceMap，并把 next 和它的新距离 newDist 一起扔进小根堆。

这样一直循环，直到堆为空，distanceMap 里就是起点到所有点的最短路径了。

import java.util.*;

// 表示图的边
class Edge {
    Node to;
    int weight;
    public Edge(Node to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

// 表示图的节点
class Node {
    int value;
    List<Edge> edges;
    public Node(int value) {
        this.value = value;
        this.edges = new ArrayList<>();
    }
}

// 堆中存放的记录，方便比较
class NodeRecord {
    Node node;
    int distance;
    public NodeRecord(Node node, int distance) {
        this.node = node;
        this.distance = distance;
    }
}

public class DijkstraAlgorithm {

    public static Map<Node, Integer> dijkstra(Node start) {
        // 从start出发到所有点的距离表
        Map<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(start, 0);

        // 已经确定了最短距离的点
        HashSet<Node> touchedNodes = new HashSet<>();

        // 选一个当前距离最小的、未被碰过的点
        Node minNode = getMinDistanceAndUntouchedNode(distanceMap, touchedNodes);

        while (minNode != null) {
            int distance = distanceMap.get(minNode);
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                // 如果当前点的邻居没在距离表里，或者新的路径更短，就更新
                if (!distanceMap.containsKey(toNode) || distanceMap.get(toNode) > distance + edge.weight) {
                    distanceMap.put(toNode, distance + edge.weight);
                }
            }
            touchedNodes.add(minNode); // 锁定这个点
            minNode = getMinDistanceAndUntouchedNode(distanceMap, touchedNodes); // 再选下一个
        }
        return distanceMap;
    }

    // 朴素的遍历查找，可以用堆来优化
    private static Node getMinDistanceAndUntouchedNode(Map<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            int distance = entry.getValue();
            if (!touchedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }

    // 堆优化的 Dijkstra
    public static Map<Node, Integer> dijkstraWithHeap(Node start) {
        Map<Node, Integer> distanceMap = new HashMap<>();
        PriorityQueue<NodeRecord> minHeap = new PriorityQueue<>(Comparator.comparingInt(r -> r.distance));

        minHeap.add(new NodeRecord(start, 0));

        while (!minHeap.isEmpty()) {
            NodeRecord record = minHeap.poll();
            Node curNode = record.node;
            int curDistance = record.distance;

            // 如果这个点已经有更短的路径被确定了，就跳过
            if (distanceMap.containsKey(curNode)) {
                continue;
            }

            // 第一次从堆里出来，就是最短距离
            distanceMap.put(curNode, curDistance);

            for (Edge edge : curNode.edges) {
                Node toNode = edge.to;
                // 只处理尚未确定最短路径的点
                if (!distanceMap.containsKey(toNode)) {
                    minHeap.add(new NodeRecord(toNode, curDistance + edge.weight));
                }
            }
        }
        return distanceMap;
    }
}

Dijkstra 的贪心之所以对，就是因为没有负权边，保证了每一步锁定的点，其距离都是最终的、不会再被更新的最小值。一旦有了负权边，这个前提就崩了，可能绕个大圈子走一个负权边，总距离反而变小了。

解法二：Bellman-Ford 算法 - 管你有没有负权边，我都能搞定

当图里出现了负权重边，Dijkstra 就歇菜了。这时候，Bellman-Ford 算法就该登场了。它比 Dijkstra 慢，但更强大，能处理负权边，甚至还能检测出负权环。

啥是负权环？就是一个环路，走一圈下来总权重是负的。这意味着你可以无限在这个环里兜圈子，路径长度可以被刷到负无穷，最短路也就没意义了。

Bellman-Ford 的思想特别朴素，有点像动态规划：

  1. 初始化所有点到起点的距离为无穷大，起点为0。

  2. 进行 N-1 轮松弛（Relaxation）操作（N是图中点的数量）。

  3. 每一轮松弛，都遍历图里的所有边。对于每一条边 u -> v，看看 distance[u] + weight(u,v) 是否比 distance[v] 更小。如果更小，就更新 distance[v]。

为啥是 N-1 轮？因为在一个不包含负权环的图里，任意两点间的最短路径最多包含 N-1 条边。第一轮松弛，能保证找到所有只需要1条边的最短路；第二轮，能找到所有最多需要2条边的最短路……以此类推，经过 N-1 轮，所有可能的最短路都被找到了。

那怎么检测负权环？很简单，在 N-1 轮松弛之后，再进行第 N 轮。如果在这一轮里，还有点的距离能被更新，那说明啥？说明图里一定存在负权环。因为所有不含环的最短路都已经找到了，还能继续变短，只能是因为陷入了一个能无限减小距离的负权环里。

import java.util.*;

public class BellmanFordAlgorithm {

    public static Map<Node, Integer> bellmanFord(Node start, List<Node> allNodes) {
        Map<Node, Integer> distanceMap = new HashMap<>();
        for (Node node : allNodes) {
            distanceMap.put(node, Integer.MAX_VALUE);
        }
        distanceMap.put(start, 0);

        // N-1 轮松弛
        for (int i = 1; i < allNodes.size(); i++) {
            // 遍历所有边
            for (Node fromNode : allNodes) {
                if (distanceMap.get(fromNode) != Integer.MAX_VALUE) {
                    for (Edge edge : fromNode.edges) {
                        Node toNode = edge.to;
                        if (distanceMap.get(fromNode) + edge.weight < distanceMap.get(toNode)) {
                            distanceMap.put(toNode, distanceMap.get(fromNode) + edge.weight);
                        }
                    }
                }
            }
        }

        // 第 N 轮检查负权环
        for (Node fromNode : allNodes) {
            if (distanceMap.get(fromNode) != Integer.MAX_VALUE) {
                for (Edge edge : fromNode.edges) {
                    Node toNode = edge.to;
                    if (distanceMap.get(fromNode) + edge.weight < distanceMap.get(toNode)) {
                        // 如果在第 N 轮还能松弛，说明有负权环
                        throw new RuntimeException("Graph contains a negative weight cycle!");
                    }
                }
            }
        }

        return distanceMap;
    }
}

Bellman-Ford 简单粗暴，时间复杂度是 O(V*E)，V是点数，E是边数。在边比较多的稠密图里，性能不如Dijkstra，但在有负权边的稀疏图里，它就是救星。

解法三：Floyd-Warshall 算法 - 我不关心起点，我全都要

前面两个算法都是单源最短路，就是算一个起点到其他所有点的最短距离。如果我现在想知道任意两个点之间的最短路怎么办？

最直接的想法是，把每个点都当成起点，跑 N 遍 Dijkstra 或者 Bellman-Ford。这当然可以，但有没有更优雅的办法？

有，那就是 Floyd-Warshall 算法。它的思想也是动态规划，而且代码极其简洁，就是三层循环。

Floyd-Warshall 的核心是：“我从点 i 到点 j，要不要经过点 k 呢？”

  1. 我们用一个二维数组 dp[i][j] 来存点 i到点 j 的最短距离。

  2. 初始化 dp[i][j]：如果 i 和 j 之间有直连的边，dp[i][j] 就是边的权重；如果 i == j，dp[i][j] 是0；否则就是无穷大。

  3. 然后我们引入一个中间点 k，从 1 遍历到 N。对于每一对 (i, j)，我们都考虑一下，i 到 j 的路径，如果把 k 作为中转站，会不会更短？ 也就是比较 dp[i][j] 和 dp[i][k] + dp[k][j] 的大小，取小的那个更新 dp[i][j]。

当 k 的循环结束时，dp 数组里就存了任意两点间的最短路径。

为啥这样是对的？当最外层循环到 k 的时候，dp[i][k] 和 dp[k][j] 已经考虑了所有编号小于 k 的点作为中转站的最优路径。所以，这一步实际上是在用编号为 1...k-1 的点作为“桥梁”的基础上，尝试再加一座新桥 k，看看能不能让路程更短。等 k 遍历完所有点，就等于考虑了所有可能的桥梁组合。

public class FloydWarshallAlgorithm {

    public static 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++) {
                dist[i][j] = graph[i][j];
            }
        }

        // k 是中间点
        for (int k = 0; k < n; k++) {
            // i 是起点
            for (int i = 0; i < n; i++) {
                // j 是终点
                for (int j = 0; j < n; j++) {
                    // 防止溢出
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        // 邻接矩阵表示图, MAX_VALUE 表示不连通
        int INF = Integer.MAX_VALUE / 2; // 防止加法溢出
        int[][] graph = {
            {0, 5, INF, 10},
            {INF, 0, 3, INF},
            {INF, INF, 0, 1},
            {INF, INF, INF, 0}
        };

        int[][] shortestPaths = floydWarshall(graph);

        for (int i = 0; i < shortestPaths.length; i++) {
            for (int j = 0; j < shortestPaths.length; j++) {
                if (shortestPaths[i][j] == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print(shortestPaths[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}

Floyd-Warshall 的时间复杂度是 O(N³)，和边的数量无关，所以它尤其适合求解稠密图的所有点对最短路问题。

总结一下

到这儿，最短路的三大金刚咱们就都认识了。怎么选？看场景：

算法适用场景能否处理负权边时间复杂度核心思想
Dijkstra单源最短路，无负权边否O(E log V) (堆优化)贪心，每次选最近的点
Bellman-Ford单源最短路，可处理负权边，可检测负权环是O(V * E)动态规划，松弛 N-1 轮
Floyd-Warshall所有点对最短路，可处理负权边是O(V³)动态规划，枚举中转点
  • #5pya55t6lev