第17章图的最短路径

课程目录第17章图的最短路径

第17章图的最短路径：三大算法的恩怨情仇

图的最短路径问题，说白了就是「怎么走最近」。

我在做网络路由协议时，天天跟这仨算法打交道。你想想看，从北京到上海，中间经过十几个城市，哪条路最短？这就是最短路径问题。

今天咱们一口气讲清楚三个经典算法：迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd）、贝尔曼-福特（Bellman-Ford）。它们各有脾气，各有适用场景。

一句话总结：

Dijkstra：单源、非负权，最快
Floyd：多源、可负权，代码最优雅
Bellman-Ford：单源、可负权，能检测负环

17.1 Dijkstra算法：贪心的胜利

Dijkstra算法是我用得最多的一个。它就像个「近视眼」——每次只看当前最近的点，然后一步步往外扩。

核心思想：

维护一个dist数组，记录起点到每个点的最短距离
每次从未访问的点中，选dist最小的那个
用这个点去更新它的邻居

我的经验： 用优先队列（小顶堆）来实现，能把时间复杂度从O(V²)降到O((V+E)logV)。我在做城市导航系统时，10万个节点用堆优化版Dijkstra，跑一次只要几十毫秒。

// Dijkstra算法 - 堆优化版
#define INF 0x3f3f3f3f
#define MAXN 100005

typedef struct {
    int to, w;
} Edge;

typedef struct {
    int u, dist;
} Node;

// 小顶堆比较函数
int cmp(const void* a, const void* b) {
    return ((Node*)a)->dist - ((Node*)b)->dist;
}

void dijkstra(int start, int n, vector<Edge> graph[]) {
    int dist[MAXN];
    int visited[MAXN] = {0};
    
    // 初始化
    memset(dist, INF, sizeof(dist));
    dist[start] = 0;
    
    // 优先队列（这里用数组模拟）
    Node heap[MAXN];
    int heapSize = 0;
    heap[heapSize++] = (Node){start, 0};
    
    while (heapSize > 0) {
        // 取出最小dist的节点
        Node cur = heap[0];
        // 简单的堆删除（实际应用请用标准堆）
        heap[0] = heap[--heapSize];
        // 这里省略了下滤操作
        
        int u = cur.u;
        if (visited[u]) continue;
        visited[u] = 1;
        
        // 松弛邻居
        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i].to;
            int w = graph[u][i].w;
            if (!visited[v] && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                heap[heapSize++] = (Node){v, dist[v]};
            }
        }
    }
}

注意： Dijkstra不能处理负权边！我曾经在一个项目中用了Dijkstra，结果图里有负权边，跑出来的结果全是错的。排查了半天才发现问题。

为什么？因为Dijkstra假设「已经确定最短路径的点不会再被更新」，但负权边会打破这个假设。

17.2 Floyd算法：优雅的暴力

Floyd算法是我见过最优雅的算法之一。代码只有几行，却能算出所有点对之间的最短路径。

核心思想： 动态规划。dp[k][i][j]表示「只经过编号≤k的中间节点」时，i到j的最短距离。

// Floyd算法 - 全源最短路径
#define INF 0x3f3f3f3f
#define MAXN 500

int dist[MAXN][MAXN];  // 距离矩阵
int path[MAXN][MAXN];  // 路径记录（可选）

void floyd(int n) {
    // 初始化
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
            path[i][j] = -1;
        }
    }
    
    // 核心三层循环
    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];
                    path[i][j] = k;  // 记录路径
                }
            }
        }
    }
}

// 打印路径
void printPath(int i, int j) {
    if (path[i][j] == -1) {
        printf("%d -> %d\n", i, j);
        return;
    }
    int k = path[i][j];
    printPath(i, k);
    printPath(k, j);
}

Floyd的优缺点：

优点：代码极简，一次算出所有点对，支持负权边
缺点：O(V³)复杂度，V超过500就开始吃力
适用场景：小规模图（V≤300）、需要频繁查询任意两点距离

我记得有一次做社交网络分析，要算所有用户之间的「距离」（共同好友数）。图只有200个节点，用Floyd简直不要太爽，代码写出来自己都感动。

17.3 Bellman-Ford算法：老实人的坚持

Bellman-Ford算法像个老实人——它不挑食，负权边也能处理，还能帮你检测出图中是否存在「负环」。

核心思想： 对所有的边做V-1次松弛操作。为什么是V-1次？因为最短路径最多包含V-1条边（没有环的情况下）。

// Bellman-Ford算法
#define INF 0x3f3f3f3f
#define MAXN 10005
#define MAXM 100005

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

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

int bellmanFord(int start) {
    // 初始化
    memset(dist, INF, sizeof(dist));
    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;  // 正常
}

负环是什么？ 就是一个环，所有边的权值之和为负数。一旦存在负环，最短路径就没有意义了——你可以绕着负环一直转，距离越来越小。

我曾经在金融套利检测系统中用过Bellman-Ford。货币兑换的汇率取负对数后，负环就对应着套利机会。嗯，这算法在金融领域也有用武之地。

17.4 三大算法对比

特性	Dijkstra	Floyd	Bellman-Ford
类型	单源	全源	单源
负权边	❌ 不支持	✅ 支持	✅ 支持
检测负环	❌	❌	✅
时间复杂度	O((V+E)logV)	O(V³)	O(V·E)
空间复杂度	O(V)	O(V²)	O(V)
适用场景	非负权稀疏图	小规模稠密图	含负权、需检测负环

17.5 如何选择？我的建议

在实际项目中，我一般这样选：

先看有没有负权边——有的话，Dijkstra直接排除
再看是单源还是全源——全源查询频繁，图又小，用Floyd
最后看要不要检测负环——要的话，只能用Bellman-Ford

小技巧： 如果图是稀疏的（边数≈节点数），Dijkstra+堆优化是最佳选择。如果图是稠密的（边数≈V²/2），用朴素Dijkstra（O(V²)）反而更快，因为堆操作的开销可能更大。

嗯，这三个算法讲完了。你想想看，它们其实代表了三种不同的思维方式：贪心（Dijkstra）、动态规划（Floyd）、暴力松弛（Bellman-Ford）。理解了这个，你就抓住了最短路径问题的本质。

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

📚 课程目录