加權有向圖的單源最短路徑問題是圖論中的經典問題。單源最短路徑問題指的是從一個節(jié)點出發(fā)膊夹，計算到圖中其它所有節(jié)點的最短路徑的問題盆昙。Dijkstra算法可以有效解決這個問題（權值不能為負數）熟掂。
對于加權有向圖中的節(jié)點v，它的任意一個前繼鄰居節(jié)點u到v的路徑(u,v)是一個獨立的路徑检号，不依賴任何其它前繼鄰居節(jié)點u'到v的路徑(u',v)。
我們在這里對圖做一個擴展蛙酪，增加一種特殊的節(jié)點齐苛，稱為匯合節(jié)點。從起始節(jié)點到匯合節(jié)點的路徑是匯合節(jié)點的一個或多個前繼鄰居節(jié)點到匯合節(jié)點的路徑的組合桂塞，組合時對各個分支距離進行加法和乘法運算凹蜂。
簡單點講，要想走到匯合節(jié)點阁危，必須先同時走到它的一個或多個前繼鄰居節(jié)點炊甲。至于具體要走過哪幾個前繼鄰居節(jié)點，要根據具體的條件要求來判斷欲芹。
這種情況在生活中經常會遇到卿啡，一件事情有多個可選的前置條件，想要完成這件事情菱父，必須先完成一個或多個前置條件颈娜。
以圖一為例：
節(jié)點d是匯合節(jié)點剑逃，這里的匯合條件是從起始節(jié)點a到d節(jié)點的路徑是其所有前繼相鄰節(jié)點的路徑的和。也就是說要想走到d官辽，必須先同時走到b和c蛹磺，然后才能計算從a到d的距離|a->d|=|a->b|+|b->d|+|a->c|+|c->d|。
對于擴展后的帶有匯合節(jié)點的加權有向圖的單源最短路徑問題應該如何解決同仆？Dijkstra算法是否依然有效萤捆？我們來分析一下這個問題。
Dijkstra算法的原理
Dijkstra算法的特點是從起始節(jié)點開始向外層層擴展俗批，直到所有節(jié)點都被訪問到俗或。
Dijkstra算法將節(jié)點分為兩組，一個是已求出最短路徑的節(jié)點的集合S（初始時只有起始節(jié)點）岁忘，另一個是未確定最短路徑的節(jié)點的集合U辛慰。每次新擴展一個距離最短的節(jié)點，更新與其相鄰節(jié)點的距離（只在相鄰節(jié)點當前的最短路徑大于經過擴展節(jié)點的路徑時更新）干像。當所有邊的權值都為正時帅腌，不會存在一個距離更短的沒擴展過的節(jié)點，所以這個節(jié)點的距離不會再被改變麻汰，將其加入到S中速客。因此，在將節(jié)點加入到S的過程中五鲫，總是保持從起始節(jié)點到S中任何節(jié)點的最短距離都不大于從起始節(jié)點到U中任何節(jié)點的最短距離溺职。從起始節(jié)點開始，直至集合U中的所有節(jié)點都轉移到了集合S中臣镣。
以圖二為例：
假設a為起始節(jié)點辅愿。從a出發(fā)，有b和c兩個相鄰節(jié)點忆某。此時需要從|ab|和|ac|中選擇一個距離最短的路徑点待。如果|ac|<|ab|，因為權值為正弃舒，所以|ac|<|ab|+|bc|一定成立癞埠，因此c一定是到a的路徑最短的節(jié)點，將c加入到集合S中聋呢。反之苗踪，如果|ab|>|ac|，所以b是到a的距離最短的節(jié)點削锰，將b加入到集合S中通铲，此時從a到c的最短路徑還要通過比較|ab|+|bc|與|ac|的大小來決定。
匯合節(jié)點引入的問題
從Dijkstra算法的原理可以看到器贩，節(jié)點向外擴展的過程中朋截，每次都要從集合U中選擇一個距離最短的節(jié)點。匯合節(jié)點的問題在于吧黄，在擴展節(jié)點時部服，無法立即計算出匯合節(jié)點的最短路徑。因為匯合節(jié)點要求對它的所有前繼相鄰節(jié)點進行組合計算拗慨，而在擴展時難以保證匯合節(jié)點的所有前繼相鄰節(jié)點都已計算出最短路徑廓八。
如果不能計算出匯合節(jié)點的最短路徑，那么就無法按照Dijkstra算法的要求選擇出距離最短的節(jié)點赵抢。此時應該如何處理剧蹂？
以圖一為例，從a出發(fā)先到達c昌讲。更新c的相鄰節(jié)點時国夜，無法計算匯合節(jié)點d的距離减噪。這種情況下應該如何處理短绸？
對匯合節(jié)點的分析
我們首先來看節(jié)點向外擴展的過程，為什么每次都要從U集合中選擇距離最短的節(jié)點筹裕？從Dijkstra算法的原理可以知道醋闭，因為需要保證不會存在距離更短的節(jié)點，從而保證被選中節(jié)點的當前路徑就是從起始節(jié)點到它的最短路徑朝卒，所以被選中節(jié)點可以放到集合S中证逻。
對于圖中的任意一個節(jié)點，如果它的相鄰節(jié)點存在匯合節(jié)點抗斤，有兩種情況：
- 匯合節(jié)點是路徑最短的節(jié)點
- 非匯合節(jié)點是路徑最短的節(jié)點
對于情況2囚企，非匯合節(jié)點會被選擇作為距離最短的節(jié)點，符合Dijkstra算法的要求瑞眼，不存在問題龙宏。
對于情況1，我們深入分析一下伤疙。
對于非匯合節(jié)點u和它的相鄰節(jié)點v银酗，我們用λu、λv表示u和v的最短路徑距離徒像，λ|uv|表示u和v之間的距離黍特，可以知道：
λv=λu+λ|uv|
=> λv>λu, λv>λ|uv|
對于匯合節(jié)點v和它的前繼相鄰節(jié)點u1,u2...uN，λv=C(λu1+λ|u1v|,λu2+λ|u2v|...,λuN+λ|uNv|)锯蛀，其中C為匯合節(jié)點v的最短路徑計算函數灭衷。可以知道對于匯合節(jié)點v的任意一個位于v的最短路徑中的前繼相鄰節(jié)點u：
λv>=∑i(λui+λ|uiv|)(i=1~N)
=> λv>=λu+λ|uv|
=> λv>λu, λv>λ|uv|
對于普通節(jié)點u旁涤、u的普通相鄰節(jié)點v以及u的匯合相鄰節(jié)點w翔曲，如果w路徑更短经备，則有λw<λv，假設組成w的最短路徑的任意前繼相鄰節(jié)點為x（x可能包括u）部默，根據上面內容可以知道:
λw<λv
λw>=λx+λ|xw|, λv=λu+λ|uv|
=> λx+λ|xw|<λu+λ|uv|
=> λx<λu+λ|uv|
=> λx<λv
如果x=u侵蒙，那么λ|uw|<λ|uv|，說明uw之間的距離小于uv之間的距離傅蹂。
如果x≠u, λx<λu纷闺，則x先于u被訪問，因而w先于v更新份蝴。
如果x≠u, λu<λx犁功，則u先于x被訪問，但是根據λx<λv婚夫，x會先于v被訪問浸卦。
根據上面的推導，如果在節(jié)點u的相鄰節(jié)點中匯合節(jié)點w的距離最短案糙，那么組成匯合節(jié)點w的最短路徑的任意前繼相鄰節(jié)點x都會優(yōu)先于u的其它任意相鄰節(jié)點v被訪問限嫌。這也就意味著匯合節(jié)點w能夠先于v被訪問。
調整Dijkstra算法
根據上面的推導时捌，對于帶有匯合節(jié)點的加權有向圖的單源最短路徑問題仍然可以使用Dijkstra算法怒医，只需做一個局部的調整：在向外擴展節(jié)點時，如果其相鄰節(jié)點中有匯合節(jié)點奢讨，則更新其對應的分支路徑的距離稚叹，但是直至匯合節(jié)點滿足了C函數可以計算完全的距離時才參與后續(xù)的最短距離節(jié)點的選擇。
示例
以圖三為例：
其中e為匯合節(jié)點拿诸，其C函數為所有前置相鄰節(jié)點構成的路徑的總和扒袖。
以a為起始節(jié)點，其計算步驟如下：
-
初始化
節(jié)點 a b c d e f g 前序訪問節(jié)點 Φ Φ Φ Φ Φ Φ Φ 距離 +∞ +∞ +∞ +∞ +∞ +∞ +∞ 訪問順序 -
訪問a節(jié)點并更新其相鄰節(jié)點的距離
節(jié)點 a b c d e f g 前序訪問節(jié)點 Φ a a Φ Φ Φ Φ 距離 0 5 6 +∞ +∞ +∞ +∞ 訪問順序 1 可以發(fā)現亩码，b是距離a路徑最短的未訪問節(jié)點季率。
-
訪問b節(jié)點并更新其相鄰節(jié)點的距離
節(jié)點 a b c d e f g 前序訪問節(jié)點 Φ a a b b? Φ Φ 距離 0 5 6 15 6? +∞ +∞ 訪問順序 1 2 可以發(fā)現，b的鄰居節(jié)點中存在匯合節(jié)點e蟀伸，我們只更新通過b到e的路徑的距離蚀同，因為還有一個前繼節(jié)點形成的路徑暫時不確定，所以無法計算e的距離啊掏，因此e不參與下一輪的選擇蠢络。
排除e之后，c是距離a路徑最短的未訪問節(jié)點迟蜜。 -
訪問c節(jié)點并更新其相鄰節(jié)點的距離
節(jié)點 a b c d e f g 前序訪問節(jié)點 Φ a a b b+c c Φ 距離 0 5 6 15 6+8=14 11 +∞ 訪問順序 1 2 3 更新c到e的路徑的距離刹孔，就可以計算a到e的距離了。
可以發(fā)現，f是距離a路徑最短的未訪問節(jié)點髓霞。 -
訪問f節(jié)點并更新其相鄰節(jié)點的距離
節(jié)點 a b c d e f g 前序訪問節(jié)點 Φ a a b b+c c f 距離 0 5 6 15 6+8=14 11 16 訪問順序 1 2 3 4 可以發(fā)現卦睹，e是距離a路徑最短的未訪問節(jié)點。
-
訪問e節(jié)點并更新其相鄰節(jié)點的距離
節(jié)點 a b c d e f g 前序訪問節(jié)點 Φ a a b b+c c e 距離 0 5 6 15 6+8=14 11 15 訪問順序 1 2 3 5 4 因為從e到g的距離比從f到e更近方库，因此更新g结序。
可以發(fā)現，d是距離a路徑最短的未訪問節(jié)點纵潦。 -
訪問d節(jié)點并更新其相鄰節(jié)點的距離
節(jié)點 a b c d e f g 前序訪問節(jié)點 Φ a a b b+c c e 距離 0 5 6 15 6+8=14 11 15 訪問順序 1 2 3 6 5 4 因為從d到g的距離比從e到g更遠徐鹤，因此不用更新g。
可以發(fā)現邀层，g是距離a路徑最短的未訪問節(jié)點返敬。 -
訪問g節(jié)點并更新其相鄰節(jié)點的距離
節(jié)點 a b c d e f g 前序訪問節(jié)點 Φ a a b b+c c e 距離 0 5 6 15 6+8=14 11 15 訪問順序 1 2 3 6 5 4 7 至此，圖中所有節(jié)點都已被訪問寥院。
我們可以發(fā)現劲赠，從a到g的最短路徑是經過匯合節(jié)點e形成的路徑，其距離為15秸谢。
