最短路算法：BFS、Dijkstra、Bellman-Ford 与 Floyd

以前看到“最短路算法：BFS、Dijkstra、Bellman-Ford 与 Floyd”，我会下意识去找一份模板保存下来。后来发现这样学得很快，忘得也快，因为BFS、Dijkstra、Bellman-Ford 和 Floyd 我分别学过，但以前选择算法时主要靠题目关键词，没有先看边权和数据规模。所以这篇不从标准答案起步，而是顺着我当时的疑问一点点往下拆。

最短路是图算法里的核心章节。很多业务问题都可以抽象成“从一个点到另一个点，代价最小的路径是什么”：地图导航、网络路由、任务成本、推荐链路、服务调用链。

但最短路不是只有 Dijkstra。选算法前，必须先看边权和查询方式。

它从哪里来

Edsger Dijkstra 在 1956 年思考图上的最短路径，并于 1959 年发表相关算法。之后不同权重条件推动了 BFS、Bellman–Ford、Floyd–Warshall 等方法的使用。选择最短路算法，首先要看边权而不是背模板。

最短路选择地图

最短路算法选择

图：最短路算法要先看边权，再看源点数量

场景	算法
无权图最少边数	BFS
非负权单源最短路	Dijkstra
存在负权边	Bellman-Ford
任意两点最短路，点数较少	Floyd
边权为 0/1	0-1 BFS

BFS 求无权最短路

无权图里，每条边成本相同。BFS 按层推进，第一次到达某个点时，就是最少边数。

int[] shortestPathUnweighted(List<List<Integer>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    Queue<Integer> q = new ArrayDeque<>();
    dist[start] = 0;
    q.offer(start);
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : graph.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.offer(v);
            }
        }
    }
    return dist;
}

如果只是无权图，不要把问题复杂化成 Dijkstra。

Dijkstra

Dijkstra 每次从未确定节点里取当前距离最小的点，并用它松弛邻居。

int[] dijkstra(List<List<int[]>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE / 2);
    dist[start] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    pq.offer(new int[]{start, 0});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0], d = cur[1];
        if (d != dist[u]) continue;
        for (int[] e : graph.get(u)) {
            int v = e[0], w = e[1];
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

堆优化 Dijkstra 的复杂度通常是 O(E log V)。

Dijkstra 的前提是边权非负。负权边会破坏“当前弹出的最小距离已经确定”这个性质。

Bellman-Ford

Bellman-Ford 能处理负权边，并能检测负环。

boolean bellmanFord(int n, int[][] edges, int start, int[] dist) {
    Arrays.fill(dist, Integer.MAX_VALUE / 2);
    dist[start] = 0;
    for (int i = 0; i < n - 1; i++) {
        boolean changed = false;
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }
        if (!changed) break;
    }
    for (int[] e : edges) {
        if (dist[e[0]] + e[2] < dist[e[1]]) {
            return false;
        }
    }
    return true;
}

返回 false 表示存在从起点可达的负环，最短路没有意义，因为可以不断绕圈让路径更短。

Floyd

Floyd 用动态规划求任意两点之间的最短路。

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

k 表示只允许经过前 k 个中转点。复杂度 O(n³)，适合点数较少、需要多源查询的场景。

工程里的最短路

工程中的最短路通常不只是算法问题，还包括建模问题：

权重代表距离、时间、成本还是风险？
权重会不会实时变化？
是否需要避开某些边？
是否需要多目标优化？
是否要求路径可解释？
是否需要缓存热门路径？

地图导航中的“最快路线”不等于“最短距离”。服务调用里的“最小成本”也可能包含延迟、失败率和资源占用。

常见错误

用 Dijkstra 处理负权图。
忘记无向图要添加双向边。
距离初始化太小，导致松弛错误。
int 溢出，应使用更大的无穷值或 long。
Floyd 三层循环顺序写错，k 必须在最外层。
负环存在时仍输出最短路。

面试题

BFS 为什么能求无权图最短路？
Dijkstra 为什么要求非负权？
Bellman-Ford 如何检测负环？
Floyd 的状态含义是什么？
什么时候应该缓存最短路结果？

小结

最短路算法选择的第一步不是写代码，而是看图的边权。无权用 BFS，非负权用 Dijkstra，负权用 Bellman-Ford，多源小图用 Floyd。真实业务里还要先定义“短”到底是什么意思。