单源点最短路径

1.基本思想
从图的给定源点到其他各个顶点之间客观上应存在一条最短路径
,在这组最短路径中,按其长度的递增次序,依次求出到不同顶点的最短路径
和路径长度
即按长度递增的次序生成各顶点的最短路径，即先
求出长度最小的一条最短路径，然后求出长度第二小的
最短路径，依此类推，直到求出长度最长的最短路径.
2 算法思想说明
设给定 源点为 Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。
当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。
设下一条最短路径终点为 Vj，则，Vj只有：
◆ 源点到终点有直接的弧 <Vs，Vj>；
◆ 从Vs 出发到Vj的这条最短路径所经过的所有中间顶点必定在S中。
即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj。

若定义一个数组 dist[n]，其每个dist[i]分量保存从 Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，
则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：
dist[i]=Min{ dist[k]| Vk∈V-S }
利用上述公式就可以依次找出下一条 最短路径
3.算法实现
设数组pre[n]保存从Vs到其他顶点的最短路径.若pre[i]=k,表示
从Vs到Vi的最短路径中,Vi的前一个顶点式Vk,

数组final[n],标示一个顶点是否加入 SAX2DTM

bool final[MAX_VEX];
int pre[MAX_VEX],dis[MAX_VEX];
void Dijkstra_path(AdjGraph *G,int v)
{
	int j,k,m,min;
	for(j=0;j<G->vexnum;j++)
	{
		pre[j]=v;final[j]=FALSE;
		dist[j]=G->adj[v][j];
	}/*各数组的初始化*/
	dist[v]=0;final[v]=TRUE;/*设置S={v}*/
	for(j=0;j<G->vexnum-1;j++)/*其余n-1个顶点*/
	{
		m=0;
		while(final[m])m++;/*找不在S 中的顶点Vk*/
		min=INFINITY;
		for(k=0;k<G->vexnum;k++)
		{
			if(!final[k]&&dist[m]<min)
			{min=dist[k];m=k;}
		}/*求出当前最小的dist[k]值*/
		final[m]=TRUE;/*将第k 个顶点并入S 中*/
		for(j=0;j<G->vexnum;j++)
		{if(!final[j]&&(dist[m]+G->adj[m][j]<distj]))
			{
				dist[j]=dist[m]+G->adj[m][j];
				pre[j]=m;
			}
		}/*修改dist 和pre 数组的值*/
		
		
	}/*找到最短路径*/
	
	
}