floyd.c

来自「数据结构--c语言」· C语言 代码 · 共 24 行

void floyd(mgraph *g,int n)
{
	int i,j,k,v,w;
	for(i=1;i<=n;i++)
	{
		if(g->arcs[i][j]!=maxint)
			p[i][j]=j;
		else
			p[i][j]=0;
		d[i][j]=g->arcs[i][j];
	}
	for(k=1;k<=n;k++)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				if(d[i][k]+d[k][j]<d[i][j])
				{
					d[i][j]=d[i][k]+d[k][j];
					p[i][j]=p[i][k];
				}
			}
	}
}