【導讀】弧頭，w為弧尾。集和弧集構(gòu)成的圖為有向圖。w之間存在一條邊。稀疏圖，否則稱作稠密圖。則稱頂點v和w互為鄰接點，和頂點v關(guān)聯(lián)的邊的數(shù)目定義為頂點v的度。路徑上邊的數(shù)目稱作路徑長度。{A,B,C,F}簡單路徑:序列中頂點不重復出現(xiàn)的路徑。若無向圖為非連通圖，一條有向路徑，則稱此有向圖為強連通圖。//在G中沒有鄰接點，則返回“空”。若w是v的最后一個鄰接點，則。//則還刪除對稱弧<w,v>。//個頂點調(diào)用函數(shù)Visit一次且僅一次。1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；應分量賦值1或清0；

　　

【正文】 而求 vl的順序應該是 按 拓撲逆序 的 次序 ； 因為拓撲逆序序列即為拓撲有序序列的 逆序列 ， 因此 應該在拓撲排序的過程中， 另設一個 “ 棧 ” 記下拓撲有序序列。 Status TopologicalOrder(ALGraph G,Stack amp。T) { FindinDdegree(G,indegree)。 InitStack(T)。 count=0。 ve[0..]=0。 while(!StackEmpty(S)) { pop(S,j)。Push(T,j)。 ++count。 for(p=[j].firstarc。 p。 p=pnextarc) { k=padjvex。 if(indegree[k]==0) Push(S,k)。 if(ve[j]+*(pinfo)=dut(j,k) ve[k]=ve[j]+*(pinfo)。 } } if(count) ruturn ERROR。 else return OK。 } Status CriticalPath(ALGraph G) { if(!TopologicalOrder(G,t)) return ERROR。 vl[0.. ]=ve[]。 while(!StackEmpty(T)) for(Pop(T,j),p=[j].firstarc。 p。p=pvextarc) { k=padjvex。 dut=*(pinfo)。 if(vl[k]dutvl[j]) vl[j]=vl[k]dut。 } for(j=0。j。++j) for(p=[j] .firstarc。 p。p=pnextarc) { k=padjvex。 dut=*(pinfo)。 ee=ve[j]。 el=vl[k]dut。 tag=(ee==el)? ?*?:?? printf(j,k,dut,ee,el,tag)。 } } 兩點之間的 最短路徑問題 ? 求從某個源點到其余各點的最短路徑 ? 每一對頂點之間的最短路徑 求 從源點到其余各點的最短路徑的算法的基本思想 : 依 最短路徑的長度 遞增的次序求得各條路徑 源點 v1 … 其中， 從源點到頂點 v的最短路徑是所有最短路徑中長度最短者。 v2 這條路徑 必定是直接從源點到該點 v1只含一條弧 ，并且這條弧的 權(quán)值最小。 下一條 路徑長度次短 的最短路徑的特點： 路徑長度最短 的最短路徑的特點： 它只可能有兩種情況：或者是 直接從源點到該點 v2(只含一條弧 )； 或者是 從源點經(jīng)過頂點 v1，再到達該頂點 v2(由兩條弧組成 )。 其余最短路徑的特點： 再下一條 路徑長度次短 的最短路徑的特點 : 它可能有三種情況：或者是 直接從源點到該點 v3(只含一條弧 )； 或者是 從源點經(jīng)過頂點 v1，再到達該頂點 (由兩條弧組成 )；或者是從源點經(jīng)過頂點 v2，再到達該頂點 v3。 它或者是 直接從源點到該點 (只含一條弧 )； 或者是 從源點經(jīng)過已求得最短路徑的頂點，再到達該頂點 。 求最短路徑的迪杰斯特拉算法： 一般情況下， Dist[k] = 源點到頂點 k 的弧上的權(quán)值 或者 = 源點到 已求出最短路徑的頂點 的路徑長度 + 已求出最短路徑的頂點 到頂點 k 的 弧上的 權(quán)值 。 設置輔助數(shù)組 Dist，其中每個分量 Dist[k] 表示 當前 所求得的從源點到其余各頂點 k 的最短路徑。 1）在所有從源點出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。 2）修改其它各頂點的 Dist[k]值。 假設求得最短路徑的頂點為 u， 若 Dist[u]+[u][k]Dist[k] 則將 Dist[k] 改為 Dist[u]+[u][k]。 ????I N F I N I TYkva r c sGkD i s t]][0[.][V0和 k之間存在弧 V0和 k之間不存在弧 其中的最小值即為最短路徑的長度。 v0 v1 v2 v3 v4 v5 100 60 10 5 50 10 30 20 ∞ 10 ∞ 30 100 D 0 1 2 3 4 5 F F F F F F final 0 1 2 3 4 5 0 ∞ 10 ∞ 30 100 ∞ 0 5 ∞ ∞ ∞ ∞ ∞ 0 50 ∞ ∞ ∞ ∞ ∞ 0 ∞ 10 ∞ ∞ ∞ 20 0 60 ∞ ∞ ∞ ∞ ∞ 0 0 1 2 3 4 5 0 1 2 3 4 5 P 鄰接矩陣 T T60 T50 90 T 60TVoid ShortestPath_DIJ(MGraph G,int v0,PathMatrix amp。P, ShortPathTable amp。D) { for(v=0。v。++v) { final[v]=FALSE。 D[v]=[v0][v]。 for(w=0。w。++w) P[v][w]=FALSE。 if(D[v]INFINITY) {P[v][v0]=TRUE。P[v][v]=TRUE。} } D[v0]=0。 fimal[v0]=TRUE。 for(i=1。i。++i){ min= INFINITY。 for(w=0。w。++w) if(!final[w]) if(D[w]min) {v=w。min=D[w]。} final[v]=TRUE。 for(w=0。w。++w) if(!final[w]amp。amp。(min+[v][w]D[w])) { D[w]=min+[v][w]。 P[w]=P[v]。 P[w][w]=TRUE。 } } } 求每一對頂點之間的最短路徑 弗洛伊德算法的基本思想是： 從 vi 到 vj 的所有可能存在的路徑中，選出一條長度最短的路徑 。 若 vi,vj存在，則存在路徑 {vi,vj} // 路徑中不含其它頂點 若 vi,v1,v1,vj存在，則存在路徑 {vi,v1,vj} // 路徑中所含頂點序號不大于 1 若 {vi,…,v 2}, {v2,…,v j}存在， 則存在一條路徑 {vi, …, v 2, …v j} // 路徑中所含頂點序號不大于 2 … 依次類推，則 vi 至 vj 的最短路徑應是上述這些路徑中，路徑長度最小者。 A B C 6 4 2 11 3 D D(1) D(0) D(1) D(2) 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 P(1) P(0) P(1) P(2) 0 1 2 0 1 2 0 1 2 0 1 2 0 AB AC AB AC AB ABC AB ABC 1 BA BC BA BC BA BC BAC BC 2 CA CA CAB CA CAB CA CAB 0 4 11 6 0 2 3 ∞ 0 A B C A B C 0 1