算法过程
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; //设顶点为字符类型typedef struct{ 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++){ for(j=0;j<n;j++){ 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} }; for(i=0;i<n;i++){ for(j=0;j<n;j++){ G.A[i][j]=a[i][j]; } } Floyd(&G,path,D,6); for(i=0;i<n;i++){//输出每对顶点间最短路径长度及最短路径 for(j=0;j<n;j++){ 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);//路径不 存在 }else{ 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;}