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

　　

【正文】 而求 vl的順序應(yīng)該是 按 拓?fù)淠嫘?的 次序 ； 因?yàn)橥負(fù)淠嫘蛐蛄屑礊橥負(fù)溆行蛐蛄械? 逆序列 ， 因此 應(yīng)該在拓?fù)渑判虻倪^程中， 另設(shè)一個(gè) “ 棧 ” 記下拓?fù)溆行蛐蛄小? 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)。 } } 兩點(diǎn)之間的 最短路徑問題 ? 求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑 ? 每一對(duì)頂點(diǎn)之間的最短路徑 求 從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想 : 依 最短路徑的長度 遞增的次序求得各條路徑 源點(diǎn) v1 … 其中， 從源點(diǎn)到頂點(diǎn) v的最短路徑是所有最短路徑中長度最短者。 v2 這條路徑 必定是直接從源點(diǎn)到該點(diǎn) v1只含一條弧 ，并且這條弧的 權(quán)值最小。 下一條 路徑長度次短 的最短路徑的特點(diǎn)： 路徑長度最短 的最短路徑的特點(diǎn)： 它只可能有兩種情況：或者是 直接從源點(diǎn)到該點(diǎn) v2(只含一條弧 )； 或者是 從源點(diǎn)經(jīng)過頂點(diǎn) v1，再到達(dá)該頂點(diǎn) v2(由兩條弧組成 )。 其余最短路徑的特點(diǎn)： 再下一條 路徑長度次短 的最短路徑的特點(diǎn) : 它可能有三種情況：或者是 直接從源點(diǎn)到該點(diǎn) v3(只含一條弧 )； 或者是 從源點(diǎn)經(jīng)過頂點(diǎn) v1，再到達(dá)該頂點(diǎn) (由兩條弧組成 )；或者是從源點(diǎn)經(jīng)過頂點(diǎn) v2，再到達(dá)該頂點(diǎn) v3。 它或者是 直接從源點(diǎn)到該點(diǎn) (只含一條弧 )； 或者是 從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn) 。 求最短路徑的迪杰斯特拉算法： 一般情況下， Dist[k] = 源點(diǎn)到頂點(diǎn) k 的弧上的權(quán)值 或者 = 源點(diǎn)到 已求出最短路徑的頂點(diǎn) 的路徑長度 + 已求出最短路徑的頂點(diǎn) 到頂點(diǎn) k 的 弧上的 權(quán)值 。 設(shè)置輔助數(shù)組 Dist，其中每個(gè)分量 Dist[k] 表示 當(dāng)前 所求得的從源點(diǎn)到其余各頂點(diǎn) k 的最短路徑。 1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。 2）修改其它各頂點(diǎn)的 Dist[k]值。 假設(shè)求得最短路徑的頂點(diǎn)為 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。 } } } 求每一對(duì)頂點(diǎn)之間的最短路徑 弗洛伊德算法的基本思想是： 從 vi 到 vj 的所有可能存在的路徑中，選出一條長度最短的路徑 。 若 vi,vj存在，則存在路徑 {vi,vj} // 路徑中不含其它頂點(diǎn) 若 vi,v1,v1,vj存在，則存在路徑 {vi,v1,vj} // 路徑中所含頂點(diǎn)序號(hào)不大于 1 若 {vi,…,v 2}, {v2,…,v j}存在， 則存在一條路徑 {vi, …, v 2, …v j} // 路徑中所含頂點(diǎn)序號(hào)不大于 2 … 依次類推，則 vi 至 vj 的最短路徑應(yīng)是上述這些路徑中，路徑長度最小者。 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