dijkstra算法过程

问题:

现已知网络拓扑图,网络中有n个节点,
现欲求拓扑图中某节点v0到v的最短路径.

原理:

初始化时将本节点加入S集合。

此最短路径长度为0，然后加入一个最小权值的邻居节点，然后更新。。。。

解决:

0.拓扑图使用有一张n*n的表G.arcs[n][n]
G.arcs[i][j]表示从节点vi到节点vj的权值,若vj于vi无直接路径相连,则为无穷大.

1.设置标志数组final[n],若final[v]=1表示节点在S集中
表示[已经]求得节点v0到节点v的最短路径.

final[v]=0则表示节点在T集中，表示[仍未]求得节点v0到节点v的最短路径.

2.设置向量D[n],表示[当前] 找到的v0到其余节点的最短路径长度,

初始状态为:若v0到vi有弧,则D[vi]为权值,否则为无穷大.

3.设置n*n的数组P[n],若P[w]=v,则表示从v0到w[当前]求得的最短路径
上倒数第二跳是v节点.

3.运行dijkstra算法,得到最短路径.

Status GetShortestPath(ALGraph G,int st,int *path)//得到st顶点与其余顶点之间的最短路径
{
	int i,v,w,weight,min;
	int final[20],D[20];//final[i]==1表示顶点i属于S集合，0表示属于T集合。
	for(i=0;i<20;i++)
		D[i]=DISTENCE_MAX;//最大值10000,D[i]表示当前顶点st到顶点i的最短距离
	for(i=0;i<20;i++)
	{
		path[i]=-1;//初始时无路径
		final[i]=0;//刚开始时全属于T集合
	}
	D[st]=0;
	final[st]=1;//先将自身标记为S集合

	for(v=FirstEdge(G,st,weight);v>0;v=NextEdge(G,st,v,weight))//st链表上的顶点
		D[v]=weight;//初始化连在st链表上的顶点

	for(i=0;i<20;i++)
	{
		if(D[i]<DISTENCE_MAX)//i是st的邻居顶点
		{	
			path[i]=st;//到顶点i的上一跳为st
		}
	}


	for(i=0;i<20;i++)//每次求得st到某个顶点的最短路径，并加到S中，然后更新到其他顶点的当前最短距离
	{
		min=DISTENCE_MAX;
		for(w=0;w<20;w++)//在T集合中循环找到当前D集合中最小的顶点,此时找到的就是最短路径
		{
			if(!final[w])//final[w]==0，即w属于T集合时执行
				if(D[w]<min)//找出当前D集合中的最小值min
				{
					v=w;
					min=D[w];
				}
		}
			//此时的顶点v就是已求出的最短路径
		final[v]=1;//将顶点v（即从st到v的最短距离已求出）加入S集

		for(w=0;w<20;w++)//更新D集合中的当前距离
		{
			FindNode(G,v,w,weight);//得到顶点v和w之间的弧,weight存储v和w之间的权值
			if( !final[w] && (min+weight)<D[w] )//顶点在T集合中 && 在v和w之间有一跳更新在T集合中的顶点
			{
				D[w]=min+weight;//更新D[w]
				path[w]=v;//到顶点w的上一跳为v
			}
		}
	}
	return 0;
}