第四部分 圖[7]

    最短路徑
　　
　　 迪傑斯特拉算法
　　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

    返回《數據結構》考研復習精編

[]  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23293.html