加權有向圖的單源最短路徑問題是圖論中的經(jīng)典問題。單源最短路徑問題指的是從一個節(jié)點出發(fā)，計算到圖中其它所有節(jié)點的最短路徑的問題。Dijkstra算法可以有效解決這個問題（權值不能為負數(shù)）。

對于加權有向圖中的節(jié)點v，它的任意一個前繼鄰居節(jié)點u到v的路徑(u,v)是一個獨立的路徑，不依賴任何其它前繼鄰居節(jié)點u'到v的路徑(u',v)。

我們在這里對圖做一個擴展，增加一種特殊的節(jié)點，稱為匯合節(jié)點。從起始節(jié)點到匯合節(jié)點的路徑是匯合節(jié)點的一個或多個前繼鄰居節(jié)點到匯合節(jié)點的路徑的組合，組合時對各個分支距離進行加法和乘法運算。

簡單點講，要想走到匯合節(jié)點，必須先同時走到它的一個或多個前繼鄰居節(jié)點。至于具體要走過哪幾個前繼鄰居節(jié)點，要根據(jù)具體的條件要求來判斷。

這種情況在生活中經(jīng)常會遇到，一件事情有多個可選的前置條件，想要完成這件事情，必須先完成一個或多個前置條件。

以圖一為例：

圖一

節(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é)點當前的最短路徑大于經(jīng)過擴展節(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é)點，有兩種情況：

1. 匯合節(jié)點是路徑最短的節(jié)點
2. 非匯合節(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的最短路徑計算函數(shù)。可以知道對于匯合節(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），根據(jù)上面內(nèi)容可以知道:

    λ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被訪問，但是根據(jù)λx<λv，x會先于v被訪問。

根據(jù)上面的推導，如果在節(jié)點u的相鄰節(jié)點中匯合節(jié)點w的距離最短，那么組成匯合節(jié)點w的最短路徑的任意前繼相鄰節(jié)點x都會優(yōu)先于u的其它任意相鄰節(jié)點v被訪問。這也就意味著匯合節(jié)點w能夠先于v被訪問。

調(diào)整Dijkstra算法

根據(jù)上面的推導，對于帶有匯合節(jié)點的加權有向圖的單源最短路徑問題仍然可以使用Dijkstra算法，只需做一個局部的調(diào)整：在向外擴展節(jié)點時，如果其相鄰節(jié)點中有匯合節(jié)點，則更新其對應的分支路徑的距離，但是直至匯合節(jié)點滿足了C函數(shù)可以計算完全的距離時才參與后續(xù)的最短距離節(jié)點的選擇。

示例

以圖三為例：

圖三

其中e為匯合節(jié)點，其C函數(shù)為所有前置相鄰節(jié)點構成的路徑的總和。

以a為起始節(jié)點，其計算步驟如下：

1. 初始化

   節(jié)點	a	b	c	d	e	f	g
   前序訪問節(jié)點	Φ	Φ	Φ	Φ	Φ	Φ	Φ
   距離	+∞	+∞	+∞	+∞	+∞	+∞	+∞
   訪問順序

2. 訪問a節(jié)點并更新其相鄰節(jié)點的距離

   節(jié)點	a	b	c	d	e	f	g
   前序訪問節(jié)點	Φ	a	a	Φ	Φ	Φ	Φ
   距離	0	5	6	+∞	+∞	+∞	+∞
   訪問順序	1

   可以發(fā)現(xiàn)，b是距離a路徑最短的未訪問節(jié)點。

3. 訪問b節(jié)點并更新其相鄰節(jié)點的距離

   節(jié)點	a	b	c	d	e	f	g
   前序訪問節(jié)點	Φ	a	a	b	b?	Φ	Φ
   距離	0	5	6	15	6?	+∞	+∞
   訪問順序	1	2

   可以發(fā)現(xiàn)，b的鄰居節(jié)點中存在匯合節(jié)點e，我們只更新通過b到e的路徑的距離，因為還有一個前繼節(jié)點形成的路徑暫時不確定，所以無法計算e的距離，因此e不參與下一輪的選擇。
   排除e之后，c是距離a路徑最短的未訪問節(jié)點。

4. 訪問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ā)現(xiàn)，f是距離a路徑最短的未訪問節(jié)點。

5. 訪問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ā)現(xiàn)，e是距離a路徑最短的未訪問節(jié)點。

6. 訪問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ā)現(xiàn)，d是距離a路徑最短的未訪問節(jié)點。

7. 訪問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ā)現(xiàn)，g是距離a路徑最短的未訪問節(jié)點。

8. 訪問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ā)現(xiàn)，從a到g的最短路徑是經(jīng)過匯合節(jié)點e形成的路徑，其距離為15。