第十五章：最短路径——Dijkstra、Bellman-Ford与Floyd-Warshall

各位同学，今天我们来聊聊图论里一个非常经典的问题——最短路径。说白了，就是在地图上找一条从A点到B点的最短路线。你想想看，导航软件、网络路由、甚至游戏里的寻路，背后都离不开这些算法。

我个人做嵌入式开发时，经常需要在资源受限的芯片上跑路径规划。那时候我才真正体会到，算法选对了，事半功倍；选错了，内存直接爆掉。嗯，今天我就把这三个最核心的算法——Dijkstra、Bellman-Ford、Floyd-Warshall——掰开揉碎了讲给你听。

最短路径算法知识体系 最短路径 Dijkstra 单源 · 非负权 · 贪心 Bellman-Ford 单源 · 负权 · 动态规划 Floyd-Warshall 全源 · 动态规划 时间复杂度 O((V+E)logV) 适合稠密图 时间复杂度 O(VE) 可检测负环 时间复杂度 O(V³) 代码最简洁 选哪个？看场景：无负权用Dijkstra，有负权用Bellman-Ford，全源用Floyd

15.1 Dijkstra算法：最经典的单源最短路径

Dijkstra算法，我愿称之为「贪心思想的典范」。它解决的是：给定一个起点，找到它到图中所有其他节点的最短路径。前提条件——图中不能有负权边。

为什么不能有负权？因为Dijkstra每次从「未处理」的节点中挑一个距离最近的，然后就不再回头更新它了。如果有负权边，后面可能出现一条更短的路径，但Dijkstra已经错过了。我在项目中就踩过这个坑——有一次用Dijkstra处理带负权的地图数据，结果路径完全不对，排查了半天才发现是数据里混了负值。

核心思路

  1. 维护一个距离数组dist[]，dist[起点]=0，其余为无穷大。
  2. 每次从「未访问」的节点中，选dist最小的那个，标记为已访问。
  3. 用这个节点去松弛它的邻居：如果dist[u] + w(u,v) < dist[v]，就更新dist[v]。
  4. 重复直到所有节点都被访问。

关键点：Dijkstra的贪心策略保证了每次选出的节点，其dist值已经是最终的最短距离。这个性质只在非负权图中成立。

代码实现（邻接表 + 优先队列）

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAXN 1000
#define INF INT_MAX

// 邻接表节点
typedef struct Edge {
    int to, weight;
    struct Edge *next;
} Edge;

Edge *graph[MAXN];
int dist[MAXN];
int visited[MAXN];
int n;  // 节点数

// 优先队列（简易实现，实际可用堆）
void dijkstra(int start) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[start] = 0;

    for (int i = 0; i < n; i++) {
        // 找未访问中dist最小的
        int u = -1, minDist = INF;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }
        if (u == -1) break;  // 剩下的不可达
        visited[u] = 1;

        // 松弛邻居
        Edge *e = graph[u];
        while (e) {
            int v = e->to;
            int w = e->weight;
            if (!visited[v] && dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
            e = e->next;
        }
    }
}

我的建议：实际工程中一定要用二叉堆或斐波那契堆来优化找最小值的操作。上面这个O(V²)的版本只适合小规模数据。我曾经在一个有5000个节点的图上跑O(V²)的Dijkstra，等了快10秒才出结果——换成堆优化后，0.1秒就搞定了。

15.2 Bellman-Ford算法：能处理负权，还能检测负环

Bellman-Ford算法，说白了就是「暴力松弛」。它不挑节点，而是对所有边进行V-1轮松弛。为什么是V-1轮？因为一条最短路径最多包含V-1条边，再多就有环了。

这个算法我最喜欢的一点是：它不仅能处理负权边，还能检测出图中是否存在负权环。如果第V轮松弛还能更新距离，那就说明有负环——路径可以无限短下去。

核心步骤

  1. 初始化dist数组，dist[起点]=0，其余为INF。
  2. 重复V-1次：遍历所有边(u, v, w)，如果dist[u] + w < dist[v]，就更新dist[v]。
  3. 再遍历一次所有边：如果还能更新，说明存在负权环。

注意：Bellman-Ford的时间复杂度是O(VE)，在稀疏图上还行，稠密图上就有点慢了。我曾经在一个有1000个节点、10万条边的图上跑Bellman-Ford，跑了将近2秒——换成SPFA（队列优化的Bellman-Ford）后，快了很多。

代码实现

#include <stdio.h>
#include <limits.h>

#define MAXN 1000
#define MAXM 10000
#define INF INT_MAX

typedef struct {
    int u, v, w;
} Edge;

Edge edges[MAXM];
int dist[MAXN];
int n, m;  // 节点数、边数

int bellman_ford(int start) {
    for (int i = 0; i < n; i++) dist[i] = INF;
    dist[start] = 0;

    // V-1轮松弛
    for (int i = 0; i < n - 1; i++) {
        int updated = 0;
        for (int j = 0; j < m; j++) {
            int u = edges[j].u;
            int v = edges[j].v;
            int w = edges[j].w;
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = 1;
            }
        }
        if (!updated) break;  // 提前结束
    }

    // 检测负环
    for (int j = 0; j < m; j++) {
        int u = edges[j].u;
        int v = edges[j].v;
        int w = edges[j].w;
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            return -1;  // 存在负环
        }
    }
    return 0;  // 正常
}

一个小技巧：如果某一轮没有任何边被松弛，就可以提前退出循环。这个优化在大多数实际场景中都能省下不少时间。我习惯在每一轮加一个updated标志位，没更新就直接break。

15.3 Floyd-Warshall算法：全源最短路径的「暴力美学」

Floyd-Warshall算法，我愿称之为「最优雅的暴力」。它用三层循环，直接算出所有节点对之间的最短路径。代码短到令人发指，但时间复杂度是O(V³)。

它的思想是动态规划：假设我们只允许经过前k个节点作为中间点，那么dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。随着k从0增加到V-1，我们逐步放开限制，最终得到全局最优。

核心代码（就这几行）

#include <stdio.h>
#include <limits.h>

#define MAXN 500
#define INF INT_MAX

int dist[MAXN][MAXN];
int n;

void floyd_warshall() {
    // k是中间节点
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (dist[i][k] == INF) continue;  // 小优化
            for (int j = 0; j < n; j++) {
                if (dist[k][j] == INF) continue;
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

使用场景：Floyd最适合节点数不超过500的稠密图。如果节点数超过1000，O(V³)的复杂度就有点吃不消了。我在一个项目中需要计算200个城市之间的最短航线距离，用Floyd简直不要太爽——代码写起来快，调试也简单。

15.4 三种算法对比

特性 Dijkstra Bellman-Ford Floyd-Warshall
问题类型 单源 单源 全源
负权边 不支持 支持 支持
负环检测 不能 能 能（通过检查对角线）
时间复杂度 O((V+E)logV) 堆优化 O(VE) O(V³)
空间复杂度 O(V+E) O(V+E) O(V²)
代码复杂度 中等（需优先队列） 简单 极简
推荐场景 无负权、稀疏图 有负权、小规模 全源、节点数少

15.5 避坑指南与个人经验

讲到这里，我想分享几个我实际踩过的坑：

  • 我曾经在Dijkstra里忘了标记已访问节点，结果死循环了。嗯，这种低级错误，犯过一次就再也不会忘了。
  • 我曾经用Floyd处理1000个节点的图，程序跑了快一分钟还没出结果——后来才发现O(V³)在V=1000时是10亿次操作，果断换方案了。
  • 我建议你在实现Bellman-Ford时，一定要加上提前退出的优化。很多教科书上的版本没有这个优化，但实际工程中它能省掉大量无意义的计算。
  • 我记得有一次在嵌入式设备上跑Dijkstra，堆的malloc/free太频繁导致内存碎片。后来我改用静态数组实现了一个简易优先队列，问题就解决了。

重要提醒：如果你用邻接矩阵存图，Floyd的代码最方便。但如果图很稀疏（边数远小于V²），用邻接表配合Dijkstra或Bellman-Ford会更省内存。我见过有人用邻接矩阵存10000个节点的图——直接爆了400MB内存，太夸张了。

好了，关于最短路径的三个核心算法，我们就讲到这里。这三种算法各有各的脾气，选对场景才能发挥最大威力。你可以在自己的项目中多试试，感受一下它们的区别。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →