5行代码搞定floyd算法
简介
floyd是图搜算法中很经典的一个算法，用于求一副图中任意两点之间的最短路径（时间，花费等）。其算法思想感觉比Dijkstra简单，而且代码也很容易实现。不过就是效率比较低，三个for循环导致复杂度为O（n3)。
实例
假如有如下的地图，图中四个点代表不同的城市，带箭头的边表示各城市间的航线（城市1可以飞到城市2，但城市2不可直接飞到城市1，只能通过其他城市周转），航线附近的数字为机票价格。
我们利用二维矩阵存储这幅地图的各个城市和每条航线的信息。
比如1号城市到2号城市的机票为2元，则设graph[1][2]的值为2。2号城市无法到达4号城市，则设置graph[2][4]的值为∞（自己设定一个较大的值即可）。另外此处约定一个城市自己飞到自己的票价为0，例如graph[1][1]为0，具体如下：
那么如何求任意城市之间最少的机票开销呢？
其实思想很简单，就是通过一个中间城市周转一下。例如从城市1直接飞到城市3需要6元，但是可以选择先从城市1飞到城市2（2元），再从城市2飞到城市3（3元），这样只需要花费2+3=5元即可。
同理，从城市4直接飞到城市3机票需要12元，而可以选择先从4飞到1（5元），再从1飞到3（6元），花费降到5+6=11元。为了省1块钱，旅途要波折一点。
如果为了丧心病狂地省钱，不怕麻烦，甚至可以先从城市4飞到城市1，然后从1飞到2，再从2飞到3，这样只需要5+2+3=10块钱，比4直飞3的12块整整省了2元。
算法思想
所以，如果要让任意两个城市（例如从顶点a点到顶点b）之间的开销变少，只能引入第三个城市（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的开销。那么这个中转的顶点k是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多点中转开销则会更少，即a->k1->k2->b或者a->k1->k2…->ki->……->b。
如果现在只允许经过1号城市，求任意两个城市之间的最低票价，应该如何求呢？只需判断graph[i][1]+graph[1][j]是否比graph[i][j]要小即可。graph[i][j]表示的是从i号城市到j号城市之间的机票花费。graph[i][1]+graph[1][j]表示的是从i号城市先到1号城市，再从1号城市到j号城市的票价之和。其中i是1~n循环，j也是1~n循环，代码实现如下：
for(i = 1;i <= n;i++) {
for(j = 1;j <= n;j++) {
if ( graph[i][j] > graph[i][1] + graph[1][j] )
graph[i][j] = graph[i][1] + graph[1][j];
}
} 在只允许通过1号城市周转的情况下，任意两个城市之间的最低机票花费更新为：
由上图可知：在只通过1号城市中转的情况下，3号城市到2号城市（graph[3][2]）、4号城市到2号城市（graph[4][2]）以及4号城市到3号城市（graph[4][3]）的票价开销都变少了。
接下来继续求在只允许经过1和2号两个城市中转的情况下任意两点之间的最低票价。此时只需要在经由1号城市周转的结果之下，加入2号城市，再判断如果经过2号城市是否可以使得i号城市到j号城市之间的票价变得更少。即判断graph[i][2]+graph[2][j]是否比graph[i][j]要小，代码实现为如下：
//经过1号顶点
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (graph[i][j] > graph[i][1]+graph[1][j])
graph[i][j]=graph[i][1]+graph[1][j];
//经过2号顶点
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (graph[i][j] > graph[i][2]+e[2][j])
graph[i][j]=graph[i][2]+graph[2][j]; 所以依次类推，只需要在最外层循环中，不断的增加可以中转的城市即可：
//多源最短路径 floyd算法（c/c++）
void floyd(int graph[][5],int points_num) {
for(int k=1;k<=points_num;k++)
for(int i=1;i<=points_num;i++)
for(int j=1;j<=points_num;j++)
if(graph[i][j]>graph[i][k]+graph[k][j])
graph[i][j]=graph[i][k]+graph[k][j];
}完整测试代码
注意矩阵从（1,1）元素开始
算法定义
define INF 999999 //定义无穷大值
#define POINTS 100 //定义城市数（顶点数）
#define EDGES 100 //定义航线数（路径数）
//创建图
void createGraph(int graph[][POINTS]) {
int mid_tmp,
points_num,
edges_num;
//获取点数 & 边数
cout<<"请输城市数量，航线数量"<<endl;
scanf("%d %d",&points_num,&edges_num);
//全部初始化为正无穷
for (int i = 1;i <= points_num;++i)
for (int j = 1;j <= points_num;++j) {
if (i == j)
graph[i][j] = 0;
else
graph[i][j] = INF;
}
cout<<"请输入各城市间的航线 ，票价"<<endl;
//输入边
int m,n,length;
for (int i = 1;i <= edges_num;++i) {
scanf("%d %d %d",&m,&n,&length);
graph[m][n] = length;
}
}
//多源最短路径 floyd算法
void floyd(int graph[][POINTS],int points_num) {
for(int k=1;k<=points_num;k++)
for(int i=1;i<=points_num;i++)
for(int j=1;j<=points_num;j++)
if(graph[i][j]>graph[i][k]+graph[k][j])
graph[i][j]=graph[i][k]+graph[k][j];
}
//输出最终的结果
void showGraph(int graph[][POINTS],int n) {
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) {
printf("%10d",graph[i][j]);
}
printf("\n");
}
}
主函数
int main(void) {
int graph[POINTS][POINTS];
createGraph(graph);
floyd(graph,4);
cout<<"任意城市最低票价图："<<endl;
showGraph(graph,4);
system("pause");
return 0;
}