29、最短路径：迪杰斯特拉（Dijkstra）算法、弗洛伊德（Floyd）算法

说到图论里的最短路径，我脑子里第一个蹦出来的场景，就是当年做导航模块时，被地图数据虐得死去活来的日子。你想想看，从一个路口到另一个路口，怎么走最近？这问题听着简单，但放到代码里，就是两种经典算法的较量——迪杰斯特拉和弗洛伊德。

今天咱们就把这两个算法掰开揉碎，看看它们到底怎么用C语言实现。嗯，先别急着看代码，咱们先把逻辑理清楚。

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

迪杰斯特拉算法，说白了就是从一个起点出发，一步步找到到所有其他点的最短路径。它有个前提——图中不能有负权边。我在项目中遇到过有人拿它去算带负权的地图，结果跑出来的路径全是错的，排查了半天才发现是算法选型出了问题。

咱们直接上代码，我习惯用邻接矩阵来存图，这样逻辑最清晰：

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

#define V 6  // 顶点数

// 找到距离起点最近且未访问的顶点
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]);
    }
}

int main() {
    int graph[V][V] = {
        {0, 2, 4, 0, 0, 0},
        {2, 0, 1, 7, 0, 0},
        {4, 1, 0, 3, 5, 0},
        {0, 7, 3, 0, 2, 6},
        {0, 0, 5, 2, 0, 1},
        {0, 0, 0, 6, 1, 0}
    };
    dijkstra(graph, 0);
    return 0;
}

弗洛伊德算法：全源最短路径的王者

迪杰斯特拉只能算一个点到其他所有点。那如果我想知道任意两个点之间的最短路径呢？这时候就该弗洛伊德算法登场了。

弗洛伊德算法的思路其实很暴力——它尝试把每个顶点都当作「中间点」，看看经过这个点能不能让路径更短。说白了就是三层循环，把所有可能性都试一遍。

代码实现比迪杰斯特拉还简洁：

#include <stdio.h>
#include <limits.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");
    }
}

int main() {
    int graph[V][V] = {
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0}
    };
    floydWarshall(graph);
    return 0;
}

两种算法的对比

咱们用一张表把它们的区别说清楚：

特性	迪杰斯特拉	弗洛伊德
适用场景	单源最短路径	全源最短路径
时间复杂度	O(V²) 或 O(E log V)	O(V³)
空间复杂度	O(V)	O(V²)
负权边	不支持	支持（但不能有负权环）
实现难度	中等	简单

我个人习惯是：如果只需要知道一个点到其他点的距离，用迪杰斯特拉。如果要做路径分析、网络拓扑计算这种需要全局信息的，直接上弗洛伊德。代码量少，不容易出错。

知识体系总览

下面这张图把本章的核心逻辑串起来了，你看一眼就能明白两个算法的定位：

实际项目中的选型建议

我在做嵌入式路由协议时，经常需要计算网络拓扑中所有节点之间的最短路径。那时候节点数也就几十个，我直接上了弗洛伊德。为什么？因为代码简单，调试方便，出bug的概率低。

但如果你是在做导航系统，起点固定，终点变化，那迪杰斯特拉更合适。我记得有一次优化车载导航模块，把弗洛伊德换成迪杰斯特拉，内存占用直接降了60%。

好了，这两个算法就聊到这儿。你想想看，一个贪心一个动态规划，一个单源一个全源，搭配起来几乎能覆盖所有最短路径的需求。下次写代码时，先问问自己：我要算几个点？图里有负权吗？选对了算法，事半功倍。

---

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