【正文】 }。tn。j++) if(D[i][k]+D[k][j]D[i][j]) { D[i][j]=D[i][k]+D[k][j]。i++) for(j=0。k++) for(i=0。} } for(k=0。 if(D[i][j]MaxInt) {P[i][j][i]=1。kn。 if(l0)D[i][j]=l。 D[i][j]=MaxInt。jn。i++) { u=GetVertex(G,i)。 for(i=0。 int i,j,k,l,t。P, DistanceMatrixamp。 typedef int** PathMatrix。 D1[i][j]=arc[i][j]。 v0 v2 3 v1 2 4 6 11 D D1 D0 D1 D2 0 1 2 0 1 2 0 1 2 0 1 2 0 0 4 11 0 4 11 0 4 6 0 4 6 1 6 0 2 6 0 2 6 0 2 5 0 2 2 3 ∞ 0 3 7 0 3 7 0 3 7 0 P P1 P0 P1 P2 0 1 2 0 1 2 0 1 2 0 1 2 0 v0v1 v0v2 v0v1 v0v2 v0v1 v0v1v2 v0v1 v0v1v2 1 v1v0 v1v2 v1v0 v1v2 v1v0 v1v2 v1v2v0 v1v2 2 v2v0 v2v0 v2v0v1 v2v0 v2v0v1 v2v0 v2v0v1 弗洛伊德 Floyd算法 int **D=new (int**[n])[n]。如果經(jīng)過頂點(diǎn) k,則最短 kpath是 從 u到 k的最短 (k1)path,再連接從 k到 v的最短 (k1)path。 cout}endl。jn。 coutP[i][0]。in。 ShortestPathDijkstra(G,0,D,P)。 int *D=new int[n]。 ()。 P[j][j]=1。(lD[w])) { D[w]=l。 if(!final[j]amp。j++) { w=GetVertex(G,j)。 //found the shortest path for(j=1。} final[k]=1。j++) //Get the minimum D[k] if(final[j]==0) //vertex j has not marked. if(D[j]min) { k=j。 for(j=1。in。 final[v0]=1。P[i][i]=1。//initial P[i][j] D[i]=(u,v)。jn。 v=GetVertex(G,i)。in。 int *final=new int[n]。 T u,v,w。 } return ( )。 i != pos) { i++。 while(!( ) amp。 } VertexIteratorT liter(G)。 if(pos0||pos=n) {cerrThere are not so many vertices!。 else return 1。 (pathData)。 = ev。 ( )) { ev = ( )。 for(( )。 adjL = GetNeighbors(sv)。 if (!FindVertex(L,ev)) {(ev)。 mincost = 。 while (!( )) { pathData = ( )。 = 0。 = sVertex。 T sv, ev。 SeqList T L, adjL。 eVertex) { PQueue PathInfo T PQ(MaxGraphSize)。 } //用優(yōu)先序列實現(xiàn)最短路徑算法 template class T int Graph T ::MinimumPath(const T amp。 a, const PathInfo T amp。 }。 template class T struct PathInfo { T startV, endV。vp長 應(yīng)當(dāng)先有 v0v p,vjk1}是已經(jīng)求得的從 v0出發(fā)的最短路徑的終點(diǎn)的集合，可以證明下一條最短路徑 (終點(diǎn) vjk),是只通過 S中頂點(diǎn)到達(dá) vjk的 。,vjk, 更新 D[i]=min{D[i], D[jk]+arc[jk][i]} 令 D[jk+1]=min{D[i], in,i≠ j1 ,j2 第二步 v3 v0 v5 v2 v4 50 v1 5 30 60 100 10 10 1 2 3 4 5 6 j D[I] 10 30 100 2 D[i] 60 4 j2=4 D[4]=30 是 v0到 v4的最短路徑的長度 20 L={v0,v2} L={v0,v2,v4} 遞歸過程：重復(fù)第二步 設(shè)已經(jīng)有 v0到 vj1 ,vj2 第一步 v3 v0 v5 v2 v4 50 v1 5 30 60 100 10 10 1 2 3 4 5 6 D[i] 10 30 100 j1=2 D[2]=10 是 v0到 v2的最短路徑的長度 20 L={v0} L={v0,v2} 迪克斯特拉 Dijkstra算法 已經(jīng)有 L={v0,v2} ，下一條最短路徑 (終點(diǎn) vj2),或者是 (v0 vj2), 或者是 (v0, vj1,vj2) 。 D[i]=從源點(diǎn) v0到頂點(diǎn) vi最短路經(jīng)的長度。 單源點(diǎn)到其余各點(diǎn)權(quán)重和最小的路徑 從 v0到其余各點(diǎn)的最短路徑 v3 v0 v5 v2 v4 50 v1 5 30 60 100 20 10 10 起點(diǎn) 終點(diǎn) 最短路徑 長度 v0 v1 v2 v3 v4 v5 (v0,v4) 30 (v0,v2) 10 (v0,v4,v3) 50 (v0,v4,v3,v5) 60 迪克斯特拉 Dijkstra算法 按路徑長度遞增逐步產(chǎn)生最短路徑 設(shè)集合 S存放已經(jīng)求出的最短路徑的終點(diǎn)，開始，S中只有一個源點(diǎn) v0，以后每求得的一條最短路徑就將終點(diǎn)加入 S，直到全部頂點(diǎn)都加入到 S. 定義一個數(shù)組 D[n]。 } 圖上兩點(diǎn)間最短距離 A D B C E F 4 6 20 14 6 6 12 8 12 2 4 10 4 五、最短路徑 兩點(diǎn)間邊數(shù)最少的路徑 可用作交通自動咨詢系統(tǒng) 兩點(diǎn)間邊權(quán)重的和最小的路徑 用來計算兩城市間路程最短， 時間最快，費(fèi)用最省的路徑 兩點(diǎn) A,B之間邊數(shù)最少的路徑 從 A點(diǎn)出發(fā)，對圖做廣度優(yōu)先遍歷。 coutendl。 coutendl。 } } } void main( ) { Graphchar G。 (i,j)。 j=()。 while(countn) { edge=( )。 (edge)。 =v。amp。 l=(u,v)。jn。i++) { u=GetVertex(G,i)。 } for(i=0。i++) { item=GetVertex(G,i)。 for(i=0。 MFSet T MFS。 T item,u,v。 //Kruskal算法 define MaxInt 32767 include include include include include typedef EdgeInfochar EI。 int cost。 } nodes[root2].parent=root1。 return FindRoot(i)。j=nodes[j].parent)； return j。 for(int j=i。} return 1。i++) if(nodes[i].data==item) { return i。 并查集類的定義 template class T int MFSet T ::Find(T item) { for(int i=0。 void Merge(int root1,int root2)。 int FindRoot(int i)。 int PTreeSize( )。 int PTreeInsert(T item, int pr)。 //number of nodes public: PTree( int m=0)。 } 樹的雙親表示法定義 template class T class PTree { PNodeT nodes[MAX_TREE_SIZE]。 雙親表示法結(jié)點(diǎn)定義 define MAX_TREE_SIZE 100 template class T struct PNode { T data。 0≠2，根不同，分支不同。 C B E A F D G H C B E A F D G H 雙親表示法 用 數(shù)組 存儲樹的結(jié)點(diǎn) 每個結(jié)點(diǎn)中附設(shè)一個字段 指示其父結(jié)點(diǎn)的位置 A B C D E F G H 0 1 2 3 4 5 6 7 A 1 B 1 C 1 D 1 E 1 F 1 G 1 H 1 A B C D E F G H 0 1 2 3 4 5 6 7 A 1 B 1 C 1 D 1 E 1 F 1 G 1 H 1 0 1 2 3 4 5 6 7 A 1 B 1 C 1 D 1 E 0 F 1 G 2 H 1 要將 AE， CG相連 只要將 E的雙親改為 0， G的雙親改為 2 A B C D E F G H 0 1 2 3 4 5 6 7 A 1 B 1 C 1 D 1 E 0 F 1 G 2 H 1 0 1 2 3 4 5 6 7 A 1 B 1 C 0 D 1 E 0 F 1 G 2 H 1 現(xiàn)在要加入邊 EG使連通度減小： 先查 E所在分支的根， E的雙親是 0，即 A點(diǎn)， A的雙親是 1， A是根。兩個結(jié)點(diǎn)各自所在分支的根相同，則他們處在