算法設計與分析 課件 第七章 分支限界 7.3.2 單源最短路徑問題

計算機算法設計與分析第7章分支限界法7.3.2單源最短路徑問題給定帶權有向圖G=(V,E),其中每條邊的權是非負實數(shù).另外,還給定V中的一個頂點,稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路徑的長度是指路徑上各邊權之和。這個問題通常稱為單源最短路徑問題。單源最短路徑問題如圖所示的有向圖G，每一條邊都有一個非負權值，求源點S到圖中各個結點之間的最短路徑。算法分析采用優(yōu)先隊列式分支限界法求解單源最短路徑問題，可以構建一個基于結點優(yōu)先級的小根堆來存放活動結點表：結點的優(yōu)先級=源點到該結點的當前路徑長度初始時源點到其余個結點之間距離長度dist[i]設置為無窮大，當然源點本身的dist[S]=0，并將源點S加入優(yōu)先隊列（小根堆）。圖的鄰接矩陣存儲到二維數(shù)組edge內。算法分析從小根堆中取出堆頂元作為當前擴展結點i，并依次檢查與結點i相鄰結點j是否滿足下列條件：dist[i]+edge[i][j]<dist[j]則更新結點j的優(yōu)先級dist[j]=dist[i]+edge[i][j]，并將j結點加入小根堆（優(yōu)先隊列）。否則被舍去處理。重復上述過程，直到小根堆(優(yōu)先隊列)為空為止。Sijdist[i]edge[i][j]dist[j]實例（1）開始時小根堆只有源點S，取堆頂元S作為擴展結點，與S相鄰的結點A，B，C，都滿足更新其優(yōu)先級條件，所以更新A、B、C的優(yōu)先級，將A、B、C結點加入小根堆，結點加入小根堆的過程中會重新調整建堆。dist[A]=dist[S]+edge[S][A]=2dist[B]=dist[S]+edge[S][B]=3dist[C]=dist[S]+edge[S][C]=4此時的解空間樹如下圖所示。SABC實例（2）取小根堆的堆頂元為A結點，與A相鄰的B、E、F結點：dist[A]+edge[A][B]>dist[B]，剪枝由A擴展的B結點。dist[E]=dist[A]+edge[A][E]=2+2=4dist[F]=dist[A]+edge[A][F]=2+7=9更新結點E,F的優(yōu)先級并將其加入堆、重新調整建堆。此時的解空間樹如下圖所示。ABCBCEF實例（3）此時，小根堆（優(yōu)先隊列）的堆頂元為優(yōu)先級最小的結點B，與B相鄰的C、D、E，只有結點D滿足優(yōu)先級更新條件而加入到堆，加入堆的過程中會重新調整建堆。dist[D]=dist[B]+edge[B][D]=3+2=5由B擴展的結點C、E被剪枝舍去。此時的解空間樹如下圖所示。BCEFCDEF實例（4）此時，堆頂元為優(yōu)先級最小的結點C，取堆頂元C,與C相鄰的結點D不滿足優(yōu)先級更新條件，剪枝由C擴展的結點D。此時的解空間樹如下圖所示。CDEFEDF實例（5）此時，堆頂元為結點E，取堆頂元E,與E相鄰的D、H，E擴展的結點D因不滿足優(yōu)先級更新條件被剪枝舍去，dist[H]=dist[E]+edge[E][H]=4+3=7結點H加入堆。此時的解空間樹如下圖所示。EDFDFH實例（6）取堆頂元結點D，與D相鄰的結點I和H，因結點H不滿足優(yōu)先級更新條件而被舍去，dist[I]=dist[D]+edge[D][H]=5+1=6結點I更新優(yōu)先級并加入堆。此時的解空間樹如下圖所示。DFHIFH實例（7）此時的堆頂元為結點I，取堆頂元I，與I相鄰的H、T,因I擴展的結點H不滿足優(yōu)先級更新條件被剪枝舍去dist[T]=dist[I]+edge[I][T]=6+2=8更新結點T優(yōu)先級并加入堆。此時的解空間樹如圖所示。IFHHFT實例（8）此時，結點H具有最高優(yōu)先級成為當前堆頂元，取堆頂元H,與H相鄰的G、T，由H擴展的結點T不滿足優(yōu)先級更新條件被剪枝舍去;dist[G]=dist[H]+edge[H][G]=7+2=9結點G加入堆。此時的解空間樹如下圖所示。HFTTFG實例（9）此時，結點T為小根堆的堆頂元。此時，若問題是求解源點S到終點T的的最短路徑，則已得到問題的解，可以提前結束循環(huán)。若需要求源點到圖中所有結點的最短路徑長度，則還需要繼續(xù)執(zhí)行，直到堆（優(yōu)先隊列）為空才結束循環(huán)。這時取堆頂元T,因T沒有出度邊的鄰結點，出堆后無操作。此時G成為當前堆頂元，擴展的結點T，且不滿足約束條件被剪枝舍去。此時的解空間樹如下圖所示。TFGGFF實例（10）到了此時，優(yōu)先隊