求任意两顶点间的最短路径的算法

[c]代码库

void ShortestPath_2 ( Mgraph G, PathMatrix *P[],DistancMatrix *D )
{/*用Floyd 算法求有向网G 中各对顶点v 和w 之间的最短路径P[v][w]及其带权长度D[v][w]。*/
	/*若P[v][w][u]为TRUE，则u 是从v 到w 当前求得的最短路径上的顶点。*/
	for ( v=0; v<G.vexnum; ++v ) /*各对顶点之间初始已知路径及距离*/
		for ( w=0; w<G,vexnum; ++w )
		{
			D[v][w]=G.arcs[v][w];
			for ( u=0; u<G,vexnum; ++u ) P[v][w][u]=FALSE;
			if ( D[v][w]<INFINITY ) /*从v 到w 有直接路径*/
			{
				P[v][w][v]=TRUE;
			}
		}
	for ( u=0; u<G.vexnum; ++u )
		for ( v=0; v<G.vexnum; ++v )
			for ( w=0; w<G.vexnum; ++w )
				if ( D[v][u]+D[u][w]<D[v][w] ) /*从v 经u 到w 的一条路径更短*/
				{
					D[v][w]=D[v][u]+D[u][w];
					for ( i=0; i<G.vexnum; ++i )
						P[v][w][i]=P[v][u][i]||P[u][w][i];
				}
}/* ShortestPath_2*/