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