图的最短路径：从单源到多源，再到拓扑与关键路径

图的最短路径问题，说白了就是「怎么走最近」。我在嵌入式项目里经常遇到这类需求——比如路由器的数据包转发、自动驾驶的路径规划，甚至智能家居中传感器数据的最优采集路线。今天咱们就把这块内容彻底讲透。

我个人习惯把图的最短路径问题分成四块来理解：单源最短路径、多源最短路径、拓扑排序、关键路径。它们之间其实有内在联系，我画了张图帮你理清思路。

一、单源最短路径：Dijkstra算法

Dijkstra算法解决的是「从一个源点到其他所有点的最短路径」。嗯，这里有个前提——图中不能有负权边。我在做嵌入式网络协议栈时，就曾用Dijkstra来计算路由表的最优下一跳。

算法的核心思想其实很简单：每次找一个离源点最近且没处理过的顶点，然后通过它去更新其他顶点的距离。说白了就是「贪心」——每次都选当前最优的。

// Dijkstra算法实现（邻接矩阵版）
#define INF 0x3F3F3F3F
#define MAXV 100

void dijkstra(int graph[MAXV][MAXV], int n, int src) {
    int dist[MAXV];      // 最短距离数组
    int visited[MAXV];   // 访问标记
    int i, j, u, min;
    
    // 初始化
    for (i = 0; i < n; i++) {
        dist[i] = graph[src][i];
        visited[i] = 0;
    }
    dist[src] = 0;
    visited[src] = 1;
    
    // 主循环
    for (i = 1; i < n; i++) {
        // 找最小dist的未访问顶点
        min = INF;
        u = -1;
        for (j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        
        if (u == -1) break;  // 剩下的顶点不可达
        visited[u] = 1;
        
        // 通过u更新邻接点
        for (j = 0; j < n; j++) {
            if (!visited[j] && graph[u][j] != INF) {
                if (dist[u] + graph[u][j] < dist[j]) {
                    dist[j] = dist[u] + graph[u][j];
                }
            }
        }
    }
    
    // 输出结果
    printf("顶点 %d 到各顶点的最短距离：\n", src);
    for (i = 0; i < n; i++) {
        printf("-> %d : %d\n", i, dist[i]);
    }
}

二、多源最短路径：Floyd算法

Floyd算法解决的是「任意两点之间的最短路径」。你想想看，如果图里有100个顶点，你要算所有点对的最短路径，用Dijkstra跑100次？那也太笨了。Floyd算法一次搞定，代码还特别简洁。

Floyd的核心思想是动态规划：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。说白了就是「看看能不能通过k点让i到j的路径更短」。

// Floyd算法实现
#define INF 0x3F3F3F3F
#define MAXV 100

void floyd(int graph[MAXV][MAXV], int n) {
    int dist[MAXV][MAXV];
    int i, j, k;
    
    // 初始化距离矩阵
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
        }
    }
    
    // 三重循环核心
    for (k = 0; k < n; k++) {          // 中间点
        for (i = 0; i < n; i++) {      // 起点
            for (j = 0; j < n; j++) {  // 终点
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }
    
    // 输出结果
    printf("任意两点间的最短距离：\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (dist[i][j] == INF)
                printf("INF ");
            else
                printf("%3d ", dist[i][j]);
        }
        printf("\n");
    }
}

三、拓扑排序

拓扑排序不是求最短路径，但它是最短路径问题的重要基础——尤其是关键路径。拓扑排序针对的是有向无环图（DAG），说白了就是把图中的顶点排成一个线性序列，使得每条边的起点都在终点之前。

举个例子：你要修一门课，必须先修完前置课程。拓扑排序就是找出一个合理的选课顺序。

// 拓扑排序（Kahn算法）
#define MAXV 100

typedef struct {
    int edges[MAXV][MAXV];
    int n;
} Graph;

void topologicalSort(Graph *g) {
    int indegree[MAXV] = {0};
    int queue[MAXV], front = 0, rear = 0;
    int i, j, count = 0;
    
    // 计算入度
    for (i = 0; i < g->n; i++) {
        for (j = 0; j < g->n; j++) {
            if (g->edges[i][j] != 0) {
                indegree[j]++;
            }
        }
    }
    
    // 入度为0的顶点入队
    for (i = 0; i < g->n; i++) {
        if (indegree[i] == 0) {
            queue[rear++] = i;
        }
    }
    
    printf("拓扑排序结果：");
    while (front < rear) {
        int v = queue[front++];
        printf("%d ", v);
        count++;
        
        // 删除v的所有出边
        for (j = 0; j < g->n; j++) {
            if (g->edges[v][j] != 0) {
                indegree[j]--;
                if (indegree[j] == 0) {
                    queue[rear++] = j;
                }
            }
        }
    }
    
    if (count != g->n) {
        printf("\n图中存在环！无法完成拓扑排序。\n");
    }
}

四、关键路径

关键路径是拓扑排序的经典应用。在AOE网（Activity On Edge）中，顶点表示事件，边表示活动，边的权值表示活动持续时间。关键路径就是「从源点到汇点最长的路径」——它决定了整个工程的最短工期。

为什么是最长路径？你想想看，工程中所有活动可以并行进行，但整个项目必须等最长的那个路径完成才能结束。所以关键路径上的活动一旦延误，整个项目就延期了。

// 关键路径算法（基于拓扑排序）
#define MAXV 100

typedef struct {
    int edges[MAXV][MAXV];  // 邻接矩阵，存储活动持续时间
    int n;
} AOE;

void criticalPath(AOE *g) {
    int ve[MAXV] = {0};     // 事件最早发生时间
    int vl[MAXV];           // 事件最迟发生时间
    int topo[MAXV];         // 拓扑序列
    int i, j;
    
    // 1. 拓扑排序并计算ve
    // ...（拓扑排序代码略，参考上一节）
    // 假设topo数组已存储拓扑序列
    
    // 2. 计算ve（正向）
    for (i = 0; i < g->n; i++) {
        int v = topo[i];
        for (j = 0; j < g->n; j++) {
            if (g->edges[v][j] != 0) {
                if (ve[v] + g->edges[v][j] > ve[j]) {
                    ve[j] = ve[v] + g->edges[v][j];
                }
            }
        }
    }
    
    // 3. 初始化vl为最大值
    for (i = 0; i < g->n; i++) {
        vl[i] = ve[g->n - 1];  // 汇点的ve就是总工期
    }
    
    // 4. 计算vl（逆向）
    for (i = g->n - 1; i >= 0; i--) {
        int v = topo[i];
        for (j = 0; j < g->n; j++) {
            if (g->edges[j][v] != 0) {  // 注意：这里是入边
                if (vl[v] - g->edges[j][v] < vl[j]) {
                    vl[j] = vl[v] - g->edges[j][v];
                }
            }
        }
    }
    
    // 5. 输出关键活动
    printf("关键活动：\n");
    for (i = 0; i < g->n; i++) {
        for (j = 0; j < g->n; j++) {
            if (g->edges[i][j] != 0) {
                int e = ve[i];                    // 活动最早开始
                int l = vl[j] - g->edges[i][j];   // 活动最迟开始
                if (e == l) {
                    printf("活动(%d->%d) 持续时间:%d\n", i, j, g->edges[i][j]);
                }
            }
        }
    }
    
    printf("总工期：%d\n", ve[g->n - 1]);
}

好了，图的最短路径这块内容就讲到这里。从单源的Dijkstra到多源的Floyd，再到拓扑排序和关键路径，你会发现它们其实是一脉相承的——都是围绕「路径」这个核心概念展开。实际项目中，选哪个算法取决于你的图有多大、有没有负权、是单源还是多源。多动手写代码，遇到问题多调试，慢慢就有感觉了。

---