160
关于对Floyd算法的思索
这个问题困扰我很久了，终于还是上机得到了证实，实践出真知啊！
将循环的顺序改为倒置一样是正确的【不论是 k，i，j 中的一个或者几个倒置，都是正确的】，如果倒置了就不能理解为：加入前K个点时的最短路，而是理解为每个点加入都是当前最短路。。。
正序之代码：
#include <stdio.h>
#define MAX 999999
int main()
{
//无向无环图的floyd
int map[6][6];
int i,j;
for(i=0;i<6;i++)
for(j=0;j<6;j++)
map[i][j]=MAX;
//自己到自己的距离是0
for(i=0;i<6;i++)
map[i][i]=0;
//init
map[1][2]=map[2][1]=10;
map[1][3]=map[3][1]=4;
map[2][3]=map[3][2]=5;
map[2][4]=map[4][2]=2;
map[4][3]=map[3][4]=1;
printf("Floyd中......\n");
//Floyd正式开始，只有四个点
int k;
for(k=1;k<=4;k++)
for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
//display
if(map[i][j]>map[i][k]+map[k][j])
{
map[i][j]=map[i][k]+map[k][j];
printf("已更新：map[%c][%c] = %d\n",i+'A'-1,j+'A'-1,map[i][j]);
}
//Floyd结束
printf("最终：\n");
for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
printf("map[%c][%c] = %d\n",i+'A'-1,j+'A'-1,map[i][j]);
return 0;
}
上面代码描述的图是：
运行结果是：
一倒序：
for(k=4;k>=1;k--) for(i=1;i<=4;i++) for(j=1;j<=4;j++)
三倒序：
for(k=4;k>=1;k--) for(i=4;i>=1;i--) for(j=4;j>=1;j--)
最后更新：2017-04-03 14:53:53