floyd算法代码随想录

### Floyd算法代码实现与解析 #### 一、Floyd-Warshall算法简介 Floyd-Warshall算法是一种用于解决加权图中最短路径问题的经典算法。此算法能够在 \(O(V^3)\) 时间复杂度内计算出所有顶点对之间的最短路径，其中 \(V\) 是图中的顶点数[^3]。 #### 二、C语言实现细节 已知邻接矩阵 `G`，存在两个二维辅助数组 `Dist[][]` 和 `Path[][]`： - `Dist[][]` 数组用来存储两顶点之间最短距离； - `Path[][]` 数组则记录了两顶点间最短路径需经过的前一个顶点索引[^4]。 以下是具体的C语言实现方式： ```c #include <stdio.h> #define INF 99999 #define MAX_V 100 void floyd(int graph[MAX_V][MAX_V], int dist[MAX_V][MAX_V], int path[MAX_V][MAX_V], int n){ int i, j, k; // 初始化dist和path for(i = 0; i < n; ++i){ for(j = 0; j < n; ++j){ dist[i][j] = graph[i][j]; if(graph[i][j] != INF && i != j) path[i][j] = i; else path[i][j] = -1; } } // 动态规划更新最短路径 for(k = 0; k < n; ++k){ for(i = 0; i < n; ++i){ for(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] = path[k][j]; } } } } } ``` 这段程序首先初始化了 `dist[][], path[][]` 数组；接着利用三重循环迭代地寻找更优解来优化每一对节点间的最小代价路径长度，并相应调整中间结点的信息[^1]。 #### 三、Python版本实现及其解释 对于希望使用更高层次编程语言的人来说，这里也给出了一版简洁明了的 Python 实现方法: ```python def floyd_warshall(graph): V = len(graph) dist = list(map(lambda i : list(map(lambda j : j , i)) , graph)) next_node = [[None]*V for _ in range(V)] for u in range(V): for v in range(V): if graph[u][v] != float('inf') and u != v: next_node[u][v] = v for k in range(V): for i in range(V): for j in range(V): # 如果通过第k个节点可以得到一条更短路劲，则更新 if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] next_node[i][j] = next_node[i][k] return dist, next_node ``` 上述Python函数接收一个表示带权重有向图的邻接矩阵作为输入参数，并返回两个列表：一个是包含了各点对间最短路径的距离表；另一个则是指示如何构建这些路径的方向指引表。这有助于后续追踪具体哪条路线构成了给定起点至终点的最佳选择。