在考研中，图的应用部分有四个大考点分别为最小生成树、最短路径问题、拓扑排序以及关键路径。在最短路径问题中有两个小考点分别为Dijkstra算法和Floyd算法。在本文，将对Floyd算法进行知识总结、讲解以及c++代码呈现。
目录
《数据结构与算法》——Floyd算法总结
目的
算法思想
手动实例
C++代码实现
参考文献
为了求解一对顶点间的最短路径，我们可以用已知的Dijkstra算法，分别将两个顶点设置为起始点执行两次Dijkstra算法，然后从得出的dist和path数组中寻找相应值即可，若是求解所有顶点间的最短路径，则需要把每个顶点分别设置为起始点共执行|v|次Dijkstra算法，此时时间复杂度为o(|v|^3)。
为解决这个问题，弗洛伊德提出了另外一种算法，被称为Floyd算法。
设定存在|v|个顶点，分别编号1、2、3…n
1.设定矩阵dist[0][][]用来保存初始直接距离arcs[][]，dist[0][i][j]表示第i个点到第j个点是否有直接连接，若有则将距离进行保存，若无联系则设置为INF(无穷大)。
2.试探地在ij两点之间添加k点，若加入k点之后距离i-k-j比直接到达的距离i-j要小，则将距离值进行更新保存，将所有的<i,j>顶点对全部进行试探加入k点计算得出的数据组成dist[k][][]数组，对k进行增长式遍历直至k = n结束最后一次试探加点。
3.此时得出了|v|个|v|*|v|的矩阵，则此时在dist[k][i][j]中对于k从0到n进行遍历，选出最靠前的最小值即为i点到j点的最短距离，而此时在<i,…,j>路径中k即为j点的前驱节点，若为零，则无中间节点。如此计算可得出path数组，此处和Dijkstra算法相同。
教材191页图7.36 (a)
1.作出邻接矩阵
零
1
2
3
1
0
4
11
2
6
0
2
3
3
INF
0
2.dists[][][]数组赋值，并开始计算。
一
1
2
3
1
0
4
11
2
6
0
2
3
3
7
0
二
1
2
3
1
0
4
6
2
6
0
2
3
3
7
0
三
1
2
3
1
0
4
6
2
5
0
2
3
3
7
0
3.选出最短路径，填写dist和path数组。
dist
1
2
3
1
0
4
6
2
5
0
2
3
3
7
0
path
1
2
3
1
0
1
2
2
3
0
2
3
3
1
0
求解完毕。
变量说明
dists[][][]：保存n个dist数组
dist[][]：保存最终的最短路径
path[]：保存最终的最短路径的前驱节点。
/*编译环境： win10专业版 DEV C++ 5.11 TDM-GCC 4.9.2 64bit */ #include<iostream> #define INF 65535 #define Max 3 #define v Max+1 using namespace std; int dists[v][v][v];//记录过程矩阵 int dist[v][v];//记录最短路径 int path[v][v];//记录路径 void Floyd(int G[][v],int n){ //初始化dists for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) dists[0][i][j] = G[i][j]; dists[0][0][i] = INF; dists[0][i][0] = INF; } //核心部分 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) dists[i][j][k] = (k==j)?0:(dists[i-1][j][k]>dists[i-1][j][i]+dists[i-1][i][k]? dists[i-1][j][i]+dists[i-1][i][k] : dists[i-1][j][k]); /* if(k==j) dists[i][j][k] = 0; else dists[i][j][k] = dists[i-1][j][k]>dists[i-1][j][i]+dists[i-1][i][k]?dists[i-1][j][i]+dists[i-1][i][k] : dists[i-1][j][k]; */ //求dist和path int temp; int min; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i == j){ path[i][j] = -1; dist[i][j] = 0; } else{ min = dists[0][i][j]; temp = i;//直接连接最近 for(int k=1;k<=n;k++)//为了找出最小边 if (dists[k][i][j] < min){ min = dists[k][i][j]; temp = k; } path[i][j] = temp; dist[i][j] = min; } } int main(){ int G[v][v]; int n = Max; //需要对G初始化 G[1][1] = 0 ; G[1][2] = 4 ; G[1][3] = 11 ; G[2][1] = 6 ; G[2][2] = 0 ; G[2][3] = 2 ; G[3][1] = 3 ; G[3][2] = INF ; G[3][3] = 0 ; Floyd(G,n); //输出 cout<<"初始G矩阵为："<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cout<<G[i][j]<<"\t"; cout<<endl; } cout<<"\n******dists矩阵组******"<<endl; for(int i=0;i<=n;i++) { cout<<"\ndist["<<i-1<<"]矩阵为："<<endl; for(int j=1;j<=n;j++) { for(int k=1;k<=n;k++) cout<<dists[i][j][k]<<"\t"; cout<<endl; } } cout<<"\ndist矩阵为："<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cout<<dist[i][j]<<"\t"; cout<<endl; } cout<<"\npath矩阵为："<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cout<<path[i][j]<<"\t"; cout<<endl; } return 0; }严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京： 清华大学出版社，2013.
王道论坛 2019年数据结构考研复习指导[M]. 北京： 电子工业出版社，2018.
如有错误，还请朋友不吝指正。
