佛洛伊德算法时间复杂度为O(n^3)，其中n为顶点的个数。

Floyd可求出任何一对顶点之间的最短路径。允许图中有带负权值的边，但是不允许有包含带负权值的边组成的回路。

#include <iostream>
using namespace std;

#define Maxsize 100
typedef char VertexType;
typedef int EdgeType;

typedef struct{
	VertexType Vex[Maxsize];
	EdgeType edge[Maxsize][Maxsize];
	int vexnum,arcnum;
}MGraph;

void Floyd(MGraph G,int A[][Maxsize],int path[][Maxsize]){
	int i,j,k;
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++){
			A[i][j]=G.edge[i][j];	//初始化
			path[i][j]=-1; 
		}
	for(k=0;k<G.vexnum;k++)	//经过k顶点 
		for(i=0;i<G.vexnum;i++)
			for(j=0;j<G.vexnum;j++)	//i->j的距离
				if(A[i][j]>A[i][k]+A[k][j]){
					A[i][j]=A[i][k]+A[k][j];
					path[i][j]=k;
				} 
}