|
最短路径 迪杰斯特拉算法 void ShortestPath_DIJ（Mgraph G int v PathMatrix &p ShortPathTable &D）{ //用Dijkstra算法求向网珠舁顶点到其余顶点v的最短路径p[v]及其带权长度d[v] //若p[v][w]为TRUE则w是从v到v当前求得最短路径上的顶点 //final[v]为true当且仅当vs已经求得v到v的最短路径 for（v=;v<Gvexnum;++v）{ inal[v]=FALSE; D[v]=Garcs[v][v]; for（w=;w<Gvexnum;++w） p[v][w]=FALSE;//设空路径 if（D[v]<INFINITY）{P[V][V]=TRUE;p[v][v]=TRUE;} }//for D[v]=; final[v]=TRUE; //开始主循环每次求得V到某个V顶点的最短路径并加V到S集 for（i=;i<Gvexnum;++i）{ min=INFINITY; for（w=;w<Gvexnum;++w） if（!final[w]） if（D[w]<min） {v=w;min=D[w];} final[v]=TRUE; for（w=;w<Gvexnum;++w） if（!final[w]&&（min+Garcs[v][w]<D[w]））{ d[w]=min+Garcs[v][w]; P[w]=P[v]; p[w][w]=TRUE; }if }//for }ShortestPath_DIJ 返回《数据结构》考研复习精编 [] [] [] [] [] [] [] [] [] [] |
