Floyd算法

算法過程

　　1，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，或者無窮大，如果兩

點之間沒有邊相連。

　　2，對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己

知的路徑更短。如果是更新它。

Floyd算法适用于APSP(All Pairs Shortest Paths)，是一種動态規劃算法，稠密圖效果

最佳，邊權可正可負。此算法簡單有效，由于三重循環結構緊湊，對于稠密圖，效率要高

于執行|V|次Dijkstra算法。

改進和優化

　　用來計算傳遞封包。

　　計算閉包隻需将Floyd中的f數組改為布爾數組，将加号改為and就可以了。

#include<stdio.h>

#include<stdlib.h>

#define MAX_VERTEX_NUM 100 //最大頂點數

#define MAX_INT 10000 //無窮大

typedef int AdjType;

typedef struct{

int pi[MAX_VERTEX_NUM];//存放v到vi的一條最短路徑

int end;

}PathType;

typedef char VType; //設頂點為字元類型

VType V[MAX_VERTEX_NUM]; //頂點存儲空間

AdjType A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //鄰接矩陣

}MGraph;//鄰接矩陣表示的圖

//Floyd算法

//求網G（用鄰接矩陣表示）中任意兩點間最短路徑

//D[][]是最短路徑長度矩陣，path[][]最短路徑标志矩陣

void Floyd(MGraph * G,int path[][MAX_VERTEX_NUM],int D[][MAX_VERTEX_NUM],int

n){

int i,j,k;

for(i=0;i<n;i++){//初始化

for(j=0;j<n;j++){

if(G->A[i][j]<MAX_INT){//判斷是否存在路徑

path[i][j]=j;

}else{

path[i][j]=-1;//或者一開始就初始化為-1，不能是零，因為a[0][0]j也為0

}

D[i][j]=G->A[i][j];

for(k=0;k<n;k++){//進行n次試探

for(i=0;i<n;i++){

if(D[i][j]>D[i][k]+D[k][j]){

D[i][j]=D[i][k]+D[k][j];//取小者

path[i][j]=path[i][k];//改Vi的後繼

int main(){

int i,j,k,v=0,n=6;//v為起點，n為頂點個數

MGraph G;

int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各頂點的最短路徑向量

int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各頂點最短路徑長度向量

//初始化

AdjType a[MAX_VERTEX_NUM][MAX_VERTEX_NUM]={

{0,12,18,MAX_INT,17,MAX_INT},

{12,0,10,3,MAX_INT,5},

{18,10,0,MAX_INT,21,11},

{MAX_INT,3,MAX_INT,0,MAX_INT,8},

{17,MAX_INT,21,MAX_INT,0,16},

{MAX_INT,5,11,8,16,0}

};

G.A[i][j]=a[i][j];

Floyd(&G,path,D,6);

for(i=0;i<n;i++){//輸出每對頂點間最短路徑長度及最短路徑

printf("V%d到V%d的最短長度:",i,j);

printf("%d\t",D[i][j]);//輸出Vi到Vj的最短路徑長度

k=path[i][j];//取路徑上Vi的後續Vk

if(k==-1){

printf("There is no path between V%d and V%d\n",i,j);//路徑不

存在

printf("最短路徑為:");

printf("(V%d",i);//輸出Vi的序号i

while(k!=j){//k不等于路徑終點j時

printf(",V%d",k);//輸出k

k=path[k][j];//求路徑上下一頂點序号

printf(",V%d)\n",j);//輸出路徑終點序号

printf("\n");

system("pause");

return 0;