这个的思想和prim的思想很像。
- 首先假设已经找到k个顶点据入口距离最短的路径,剩余(n-k)个顶点距离入口的最短距离也知道。
- 再寻找下一个加入路径的顶点时,首先寻找剩余(n-k)个顶点距离最短的顶点,加入路径。
- 加入路径后需要更新剩余(n-k-1)个顶点距离入口的最短距离。由于新加入了第m=K+1个顶点,对于剩余的任意一个顶点Vi,只要比较Vi不经过Vm到入口的距离和经过Vm到入口的距离,如果后者更短,需要更新顶点Vi距离入口的最短距离的信息。
在这里用了3个辅助数组。
- final[v]=1,表示顶点v已经加入了路径了。即顶点v距离入口的最短距离已经找到。
- pathArc[v]的值表示,顶点v到入口最短路径的前一个顶点。
- pathTable[v]表示顶点v到入口最短路径的长度。
代码:
void ShortestPathDijkstra(Mgraph* G,int vFrist,int *&pathArc,int *&pathTable) { int v,i,k,min; int *final=(int*)malloc(sizeof(int)*G->numVertexs); pathArc=(int*)malloc(sizeof(int)*G->numVertexs); pathTable=(int*)malloc(sizeof(int)*G->numVertexs); for (v=0;v<G->numVertexs;v++) { final[v]=0; pathArc[v]=0; pathTable[v]=G->arc[vFrist][v]; } final[vFrist]=1; for (v=1;v<G->numVertexs;v++) { min=INFINITY; //寻找距离vFrist最近的顶点,也就是pathTable数组中的最小值 for (i=0;i<G->numVertexs;i++) { if (!final[i]&&pathTable[i]<min) { min=pathTable[i]; k=i; } } final[k]=1; //更新图中剩余的顶点与vFrist的距离, //现在pathTable数组中的值表示除已经加入路径(final值为1)以外的顶点与vFrist的距离。 //遍历图中所有顶点,去掉已经加入路径的,比较每个顶点在Vk加入路径后比之前的距离,如果短就更新pathTable的值。 //pathArc的值表示在当前的路径中,顶点Vi与Vfrist要想距离最短,需要链接到pathArc[Vi]顶点。 for (i=0;i<G->numVertexs;i++) { if (!final[i]&&(min+G->arc[k][i])<pathTable[i]) //min中存放着顶点Vk到Vfrist的最短距离。 { pathTable[i]=min+G->arc[k][i]; pathArc[i]=k; } } } }