Dijkstra算法求最短路径

[c]代码库

void ShortestPath_1 ( Mgraph G,int v0,PathMatrix *p, ShortPathTable *D )
{ /*用Dijkstra 算法求有向网G 的v0 顶点到其余顶点v 的最短路径P[v]及其路径长度D[v]*/
	/*若P[v][w]为TRUE，则w 是从v0 到v 当前求得最短路径上的顶点*/
	/*final[v] 为TRUE 当且仅当v∈S, ，即已经求得从v0 到v 的最短路径*/
	/*常量INFINITY 为边上权值可能的最大值*/
	for ( v=0; v<G.vexnum; ++v )
	{
		fianl[v]=FALSE;
		D[v]=G.edges[v0][v];
		for ( w=0; w<G.vexnum; ++w ) P[v][w]=FALSE; /*设空路径*/
		if ( D[v]<INFINITY ) {P[v][v0]=TRUE; P[v][w]=TRUE;}
	}
	D[v0]=0;
	final[v0]=TRUE； /*初始化，v0 顶点属于S 集*/
	          /*开始主循环，每次求得v0 到某个v 顶点的最短路径，并加v 到集*/
	          for ( i=1; i<G.vexnum; ++i ) /*其余G.vexnum-1 个顶点*/
	{
		min=INFINITY; /*min 为当前所知离v0 顶点的最近距离*/
		for ( w=0; w<G.vexnum; ++w )
			if ( !final[w] ) /*w 顶点在V－S 中*/
				if ( D[w]<min ) {v=w; min=D[w];}
		final[v]=TRUE /*离v0 顶点最近的v 加入S 集合*/
		         for ( w=0; w>G.vexnum; ++w ) /*更新当前最短路径*/
			         if ( !final[w]&& ( min+G.edges[v][w]<D[w] ) ) /*修改D[w]和P[w],w∈V-S*/
			{
				D[w]=min+G.edges[v][w];
				P[w]=P[v];
				P[w][v]=TRUE; /*P[w]=P[v]+P[w]*/
			}
	}
}/*ShortestPath._1*/