21. 最短路径：迪杰斯特拉算法与弗洛伊德算法

说到图论里的最短路径，我估计很多朋友第一反应就是导航软件里的路线规划。没错，这确实是它最经典的应用场景。但在我多年的嵌入式开发经历中，最短路径的应用远不止于此——比如网络路由协议、城市交通调度，甚至芯片内部的布线优化，背后都离不开这两个算法。

今天咱们就来聊聊两个最核心的算法：迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。一个适合单源最短路径，一个适合全源最短路径。说白了，一个是从一个点出发找所有点的最短距离，另一个是找出所有点两两之间的最短距离。

21.1 迪杰斯特拉算法：单源最短路径的利器

先说说迪杰斯特拉。我个人习惯把它叫做“贪心+松弛”的经典组合。它的核心思想其实很简单：每次从还没处理过的节点中，挑一个距离起点最近的节点，然后尝试通过这个节点去更新其他节点的距离。

嗯，这里要注意：它要求图中不能有负权边。为什么？因为一旦有负权边，你之前认为“最近”的节点可能并不是真的最近，贪心策略就失效了。我在项目中遇到过有人拿它去处理带负权的图，结果跑出来的路径完全不对，排查了半天才发现是图本身的问题。

算法步骤

1. 初始化：起点到自身的距离为0，到其他所有节点的距离为无穷大。
2. 维护一个已访问集合S，初始为空。
3. 从未访问的节点中，选出距离起点最近的节点u。
4. 将u加入S，然后遍历u的所有邻接节点v，尝试更新dist[v] = min(dist[v], dist[u] + weight(u, v))。
5. 重复步骤3-4，直到所有节点都被访问。

代码实现

下面是我写的一个标准实现，用的是邻接矩阵。你想想看，如果图比较稀疏，其实用邻接表+优先队列会更高效。

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

#define V 9  // 顶点数

int minDistance(int dist[], int visited[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (!visited[v] && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int visited[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }
    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, visited);
        visited[u] = 1;

        for (int v = 0; v < V; v++)
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    printf("顶点\t距离起点\n");
    for (int i = 0; i < V; i++)
        printf("%d\t%d\n", i, dist[i]);
}

时间复杂度分析

实现方式	时间复杂度	适用场景
邻接矩阵 + 线性查找	O(V²)	稠密图
邻接表 + 优先队列	O((V+E)logV)	稀疏图

21.2 弗洛伊德算法：全源最短路径的优雅解法

弗洛伊德算法就完全是另一种思路了。它用的是动态规划，说白了就是：从i到j的最短路径，要么直接走，要么经过某个中间节点k。它一次计算就能得到所有节点对之间的最短路径，非常优雅。

我曾经在一个物流调度系统里用过它。当时需要计算全国几十个城市之间的最短运输距离，用弗洛伊德算法一次跑完，后面所有查询都是O(1)的查表操作，爽得很。

核心递推公式

设dist[i][j]表示从i到j的最短路径长度，那么：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

这个公式对所有k从0到V-1进行迭代。每次迭代，我们都尝试让k作为中间节点，看看能不能让路径更短。

代码实现

#include <stdio.h>
#define V 4
#define INF 99999

void floydWarshall(int graph[V][V]) {
    int dist[V][V];

    // 初始化距离矩阵
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    // 核心三重循环
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    // 打印结果
    printf("最短路径矩阵：\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf("%7d", dist[i][j]);
        }
        printf("\n");
    }
}

21.3 两种算法的对比

特性	迪杰斯特拉	弗洛伊德
解决的问题	单源最短路径	全源最短路径
时间复杂度	O(V²) 或 O((V+E)logV)	O(V³)
空间复杂度	O(V)	O(V²)
能否处理负权边	不能	可以（但不能有负权环）
适用场景	从一个源点出发	需要所有点对距离

21.4 知识体系结构图

下面这张图帮你理清这两个算法的核心脉络：

21.5 避坑指南与实战建议

最后，我结合自己的踩坑经历，给你几个实用建议：

• 图中有负权边怎么办？别用迪杰斯特拉，改用贝尔曼-福特算法。我曾经在项目中因为没注意这个细节，调试了整整两天。
• 节点数超过1000时，弗洛伊德算法基本不可用。这时候可以考虑多次调用迪杰斯特拉（每个节点作为源点一次），或者用约翰逊算法。
• 如果你只需要知道某两个点之间的最短路径，别傻傻地跑全源算法。迪杰斯特拉一次就够了。
• 路径记录：在实际应用中，我们往往不仅需要最短距离，还需要具体的路径。记得在松弛操作时同步更新前驱节点数组。

好了，关于最短路径的两个经典算法就聊到这里。代码我已经贴出来了，建议你亲手跑一跑，改改参数，看看结果的变化。只有亲手写过，才能真正理解“松弛”和“动态规划”到底是怎么回事。

---

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