//此代码综合网络上的代码。
//弗洛伊德算法Floyd代码
//杨鑫
#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;int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点的最短路径向量
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//v到各顶点最短路径长度向量 //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;}D[i][j]=G-&