关于弗洛伊德算法

弗洛伊德算法是求多源最短路径的一种算法。

算法要点：

对于每一对顶点u和v，看看是否存在一个顶点w使得u到w再从w到v比已知路径更短，如果是则更新它。该算法是一种动态规划算法，稠密图效果最佳，边权可正可负。

缺点：时间复杂度较高，不适合计算大量数据。

时间复杂度：N^3

代码：

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"
#include <stdio.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535

typedef struct//定义图
{
	int vexs[MAXVEX];
	int arc[MAXVEX][MAXVEX];
	int Nv,Ne;//点数，边数
}MGraph;

typedef int parc[MAXVEX][MAXVEX];
typedef int ShortPath[MAXVEX][M];

void CreateG(MGraph *G)
{
	int i,j;
	
	G->Ne=16;
	G->Nv=9;
	for(int i=0;i<G->Nv;i++)
	{
		G->vexs[i]=i;
	}
	for(i=0;i<G->Nv;i++)
	{
		if(i==j)
			G->arc[i][j]=0;
		else
			G->arc[i][j]=G->arc[j][i]=INFINITY;
	}
}

G->arc[0][1]=1;
	G->arc[0][2]=5; 
	G->arc[1][2]=3; 
	G->arc[1][3]=7; 
	G->arc[1][4]=5; 

	G->arc[2][4]=1; 
	G->arc[2][5]=7; 
	G->arc[3][4]=2; 
	G->arc[3][6]=3; 
	G->arc[4][5]=3;

	G->arc[4][6]=6;
	G->arc[4][7]=9; 
	G->arc[5][7]=5; 
	G->arc[6][7]=2; 
	G->arc[6][8]=7;

	G->arc[7][8]=4;
for(i=0;i<Nv;i++)
{
	for(j=i;j<Nv;j++)
	{
		G->arc[j][i]=G->arc[i][j];
	}
}

void Floryed(MGraph G,parc *P,ShortPath *D)
{
	int v,w,k;
	for(v=0;v<G->Nv;++v)//初始化D与P
	{
		for(w=0;w<Nv;++w)
		{
			(*D)[v][w]=G.arc[v][w];
			(*P)[v][w]=w;
		}
	}
	for(k=0;k<G->Nv;k++)
	{
		for(v=0;v<G-Nv;v++)
		{
			for(w=0;w<G->Nv;w++)
			{
				if((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
				{
					(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
					(*P)[v][w]=(*P)[v][k];
				}
			}
		}
	}
}