vertex-disjoint path

path的分類

open path / closed path:起點終點不相同/相同。頭尾不銜接/銜接。

simple path / non-simple path:點邊不重複/重複。現在已經很少人使用這個定義。

vertex-disjoint path / edge-disjoint path:點不可重複(邊也不可重複)/邊不可重複(點可以重複)。

目前有兩套定義,定義產生衝突。

path有兩種意思。自己小心。

old-fashioned         | new-style   | allow    | allow
definition            | definition  | repeated | repeated
                      |             | vertices | edges
======================+=============+==========+=========
path                  | walk        |    ✓     |    ✓
edge-disjoint path    | trail       |    ✓     |
vertex-disjoint path  | path        |          |
----------------------+-------------+----------+---------
cycle                 | closed walk |    ✓     |    ✓
edge-disjoint cycle   | circuit     |    ✓     |
vertex-disjoint cycle | cycle       |          |

尚無正式中文翻譯。

舊版定義 |新版定義 |意義
一一一一一十一一一一一十一一一一一一一一一一一一一一一一一一一一一一
路徑   |走道/漫步|可以重複經過同樣的點和邊。
邊互斥路徑|跡    |可以重複經過同樣的點,沒有重複經過同樣的邊。
點互斥路徑|路徑   |沒有重複經過同樣的點和邊。
一一一一一十一一一一一十一一一一一一一一一一一一一一一一一一一一一一
環    |封閉走道 |可以重複經過同樣的點和邊。
邊互斥環 |迴路   |可以重複經過同樣的點,沒有重複經過同樣的邊。
點互斥環 |環    |沒有重複經過同樣的點和邊。

vertex-disjoint path

「點互斥路徑」。點不重複的路徑。想當然邊也不重複。

shortest path

shortest path

「最短路徑」。點與邊可以重複的最短路徑。

最短路徑是P問題。先前已經介紹許多演算法,不再贅述。

shortest vertex-disjoint path

「最短點互斥路徑」。點(與邊)不重複的最短路徑。

需要區分無向圖、有向圖。需要區分有無負邊、有無負環。

最短點互斥路徑是NP-complete問題。當圖上確定沒有負環,才是P問題。

       丨   丨無負邊    丨有負邊、無負環丨有負環
一一一一一一一十一一一十一一一一一一一十一一一一一一一十一一一一一一
最短路徑   丨無向圖丨即是點互斥路徑丨長度負無限大 丨長度負無限大
       丨有向圖丨即是點互斥路徑丨即是點互斥路徑丨長度負無限大
一一一一一一一十一一一十一一一一一一一十一一一一一一一十一一一一一一
最短點互斥路徑丨無向圖丨先前的演算法 丨T-join (?)  丨NP-complete
       丨有向圖丨先前的演算法 丨先前的演算法 丨NP-complete

無向圖。如果有負邊,「最短路徑」來回走負邊,長度成為負無限大。如果無負邊,「最短路徑」等於「最短點互斥路徑」。

有向圖。如果有負環,「最短路徑」不斷繞負環,長度成為負無限大。如果無負環,「最短路徑」等於「最短點互斥路徑」。

無向圖無負邊、有向圖無負環,「最短路徑」決不重複走過同樣的點和邊而導致長度增加。「最短路徑」等於「最短點互斥路徑」。

longest vertex-disjoint path

最長點互斥路徑問題當中,每一條邊的權重添上負號,就變成最短點互斥路徑問題。反過來也是。

最長點互斥路徑是NP-complete問題。當圖上確定沒有正環,才是P問題。

k shortest path

k shortest path

「第k短路徑」。一張圖,給定起點與終點,排名第k短的路徑。可能跟最短路徑一樣長。

引用Dijkstra's algorithm。DP表格弄大一點,每個點都儲存前k短的長度。時間複雜度O(K (E + VlogV))。

UVa 10740

k shortest vertex-disjoint path

目前沒有高速演算法。大多使用窮舉法,窮舉所有可能的路徑。時間複雜度本是指數時間,但如果配合了heuristic function,理想狀態之下,時間複雜度得宣稱是多項式時間。

演算法有Yen's algorithm與Martins–Pascoal–Santos algorithm。

ICPC 3624

next-to-shortest path

strictly second shortest path(next-to-shortest path)

「嚴格次短路徑」。給定起點與終點,權重不等於最短路徑、權重盡量小的路徑。可能有許多條。

不想走這條路,就必須改走別條路。不想走最短路徑,而想走嚴格次短路徑,那就先列出所有的最短路徑,再尋找別條路。

一張圖,給定起點與終點,所有的最短路徑形成了「最短路徑圖」。圖上只有正邊時,最短路徑圖是有向無環圖DAG;圖上只有零邊負邊、沒有負環時,最短路徑圖可能額外出現零環。

有向圖,嚴格次短路徑一定經過「最短路徑圖」以外的邊。

無向圖,嚴格次短路徑還可以逆行「最短路徑圖」上面的邊。

無論有向圖還是無向圖,將嚴格次短路徑定義成有向邊,比較方便。

替代路線太長,於是觀察其中一條邊,此處暫稱為替代邊。嚴格次短路徑越短越好。當有一條路徑經過替代邊xy,要使此路徑盡量短,唯一的方法就是:從起點s到x必須是最短路徑,從y到終點t也必須是最短路徑。然後使用窮舉法,窮舉所有可能的替代邊,即可找到其中一條嚴格次短路徑。

一、預先計算起點s出發的單源最短路徑。
二、預先計算抵達終點t的單源最短路徑。
三、窮舉圖上每一條邊xy作為替代邊(無向圖則視作雙向都有邊):
 甲、取得最短路徑s⤳x。
 乙、取得最短路徑y⤳t。
 丙、串成一條路徑s⤳x→y⤳t。
  回、若s⤳x→y⤳t是最短路徑,表示邊xy不是替代邊,捨棄之。
    因為最短路徑有許多條,所以取其長度,再用長度做判斷。
  回、若s⤳x→y⤳t不是最短路徑,就有可能是嚴格次短路徑,記錄之。
    當中最短者,便是嚴格次短路徑。

時間複雜度等同於單源最短路徑。

UVa 10342

strictly second shortest vertex-disjoint path

仿效前面段落,分為兩種情況「經過最短路徑圖的邊與以外的邊」與「經過最短路徑圖的邊與反方向邊」。

s⤳x→y⤳t必須是點互斥路徑。最短路徑圖,尋找從s往x跨y的替代路徑入口x',尋找從y往t跨x的替代路徑出口y',同時確保替代路徑不相交,最後改成計算路徑s⤳x'→y'⤳t。我沒能弄懂細節,請讀者自行研究原始論文。

replacement path

replacement path

道路崩塌、道路阻塞,如何找到最短的替代道路呢?

一張圖,給定起點與終點。切斷圖上一條邊之後,新的最短路徑,稱作此邊的「替代路徑」,可能不存在(長度無限大)、可能有許多條。

bridge of shortest-path graph

觀察最短路徑圖。刪除橋,才會改變最短路徑長度,才有討論意義。

當圖上只有正邊零邊,橋的兩側仍是單源最短路徑圖。替代路徑是另一座橫跨兩側的橋。窮舉所有橫跨兩側的橋,就能找到最短的替代路徑。

當圖上有負邊,終點側不見得是單源最短路徑圖。目前尚未出現特殊演算法,只能刪除橋之後,以新圖找最短路徑。

無向圖,替代路徑是另一座橫跨兩側的橋,替代路線是最短路徑、橋、最短路徑。

有向圖,替代路線不一定是另一座橫跨兩側的橋。【尚待確認】

shortest path的銜接與斷開

一、a⤳b、b⤳c是最短路徑,那麼a⤳b⤳c是不是最短路徑?

不一定。此即relaxation的用途。

二、a⤳b⤳c是最短路徑,那麼a⤳b、b⤳c是不是最短路徑?

不一定。只有正邊零邊則是,有負邊則不一定。例如路徑b⬿c為負值,那麼從a到b的最短路徑可能是a⤳c⤳b,往回走負邊,爭取更短的長度。例如路徑a⬿b為負值,那麼從b到c的最短路徑可能是b⤳a⤳c,往回走負邊,爭取更短的長度。

演算法(Malik–Mittal–Gupta algorithm)

適用於無向圖,只有正邊零邊、沒有負邊。用來找到圖上每一條邊的其中一條替代路徑。不過我們通常只關心最短路徑圖上的橋。

兩棵最短路徑樹,起點側逐步延展、終點側逐步削減。隨時記錄當下所有橋,隨時求得次佳的橋。所有橋塞入priority queue,加快速度。

時間複雜度O(ElogE)。可以改寫成O(ElogV)。

演算法(Nardelli–Proietti–Widmayer algorithm)

適用於無向圖,只有正邊零邊、沒有負邊。

最短路徑樹,視作生成樹,視作fundamental cycle basis,每一條cross edge都是替代路徑。

採用「transmuter」資料結構,以逆向拓樸順序,求得最短替代路徑。

時間複雜度O(Eα(V))。

replacement vertex-disjoint path

我沒有研究。

graph center

eccentricity

eccentricity(i) = max d(i, j)
                  j∊V

d(i, j) 為i點到j點的最短路徑

在一張無向圖上面,給定圖上一點,以最短路徑長度當作距離,找出離此點最遠的一點,這兩點之間的距離就叫做「偏心距」。

diameter / radius

diameter(G) = max eccentricity(i) = max d(i, j)
              i∊V                  i,j∊V

radius(G)   = min eccentricity(i)
              i∊V

一張無向圖的「直徑」是圖上所有偏心距當中最大的一個,一張無向圖的「半徑」是圖上所有偏心距當中最小的一個。「直徑」也可以直接想做是,一張圖上長度最長的一條最短路徑之長度。

【註:有時候為了方便,直徑和半徑會定義成一段路徑,而不是一個數值。】

一張圖可能會有許多條直徑、許多條半徑。

直徑和半徑都是最短路徑。根據最短路徑的性質,直徑和半徑中間截取一段路徑,也是最短路徑。

要計算一張無向圖的直徑與半徑是很簡單的,首先算好所有兩點之間最短路徑,然後按照定義來算就可以了。

ICPC 3569

peripheral vertex

central vertex(center)

center(G) = arg min eccentricity(i)
             i  i∊V

          = arg min max d(i, j)
             i  i∊V j∊V

d(i, j) 為i點到j點的最短路徑

一張無向圖的「中心」是圖上的一個點,離中心最偏遠的點,其距離會最小,也就是說「中心」的偏心距會等於半徑長度。一張無向圖可能會有很多個「中心」。

中心離圖上所有點越近越好,圖上所有點離中心越近越好。是以最偏遠的點的距離來衡量遠近,而非以各點的距離總和來衡量遠近。

要找到一張無向圖的中心是很簡單的,首先算好所有兩點之間最短路徑,然後按照定義來找就可以了。

absolute center

absolute_center(G) = arg min eccentricity(i)
                      i   i

                   = arg min max d(i, j)
                      i   i  j∊V

一張無向圖的「絕對中心」,與中心稍有不同。絕對中心不一定得是原圖上的點,它可以位於某條邊上的某處。一張無向圖可能會有很多個「絕對中心」。

演算法(Kariv–Hakimi algorithm)

此演算法跟一般圖論問題的解題手法完全不同。首先忘掉圖論,讓我們回到高中函數。

我們先假設絕對中心在邊ij上面。接著畫出一個函數圖形:X軸是絕對中心與i點的距離(想當然X軸範圍只有0到d(i,j)),Y軸是絕對中心與圖上x點的最短距離。先隨便選一個x點。

根據絕對中心在邊ij上面的各種位置,我們都可以算出絕對中心離x點的最短距離,進而描出一條函數線。這條函數線長得什麼樣子呢?以下分為三種情況討論:

甲、絕對中心在正權重的邊上游移:

觀察絕對中心到x點的最短距離變化。絕對中心挪往邊ij的中間,絕對中心到x點的最短距離就會慢慢增加;絕對中心挪往邊ij的兩端,絕對中心到x點的最短距離就會慢慢減少。左右的坡度是相同的,也可能只有左坡或者只有右坡。

接著觀察絕對中心到圖上每一點的最短距離變化。我們可以把每一個點的函數線統統描在同一張函數圖形,每條線的坡度都是一樣的。

根據絕對中心的定義,絕對中心與最遠點的距離越小越好;對照到函數圖形,就是上方邊際線的Y軸座標越低越好。由此可知,上方邊際線的最凹處,就是絕對中心的偏心距大小;最凹處的投影位置,就是絕對中心的最佳位置。窮舉上方邊際線的所有凹處,找出最小的偏心距,就能找到絕對中心。

該如何找到上方邊際線的最凹處呢?這就要一點小技巧了。首先把每一條函數線的左端點按照高低排序,然後由最高的函數線開始,不斷與更低的函數線相交,交點即是上方邊際線的凹處。每次求得交點後,就留下原本較低的函數線,繼續與更低的函數線相交,最後就能得到所有凹處。Y軸座標最低的,就是最凹處了。

計算凹處的Y軸座標很簡單,只需要知道相交的兩條線在X軸的兩端分別有多高,就能推導出來了:

  eccentricity(c)
= d(c, i) + d(i, x)
= d(c, j) + d(j, y)
= (d(i, j) + d(i, x) + d(j, y)) / 2

乙、絕對中心在負權重的邊上游移:

X軸左右兩端最高的函數線的交叉點,就是上方邊際線的最凹處。輕鬆寫意。

丙、絕對中心在零權重的邊上游移:

函數線都是水平線,最高的函數線到處都是最凹處。

最後,要找到一張無向圖的絕對中心,只需窮舉圖上所有邊,看看絕對中心在哪一條邊,再來依照方才的分析過程,取偏心距最小者即可。

一、計算所有兩點之間最短路徑。
  並且記錄起點到圖上各點的最短路徑長度順序。
二、窮舉圖上所有邊ij,找出絕對中心:
 甲、正邊:i點、j點、上方邊際線所有凹處。O(V)。
 乙、負邊:i側最高線與j側最高線的交叉點。O(1)。
 丙、零邊:最高的水平線。O(1)。

時間複雜度

一、計算所有兩點之間最短路徑:有負邊,以minimum weight T-join求解,O(V⁴);無負邊,執行V次Dijkstra's algorithm,以Fibonacci heap實作,O(V(E + VlogV))。

二、尋找絕對中心:圖的資料結構為adjacency lists是O(VE)。

時間複雜度取決於計算最短路徑的時間。

實作

下面提供一個簡化過的實作,假設圖上的邊都是正權重。

這段程式碼沒有特別記錄絕對中心的位置,各位可以試著想一下怎麼記錄。

延伸閱讀:無權重圖的絕對中心

簡單來說,就是每一條邊的權重都是一。在這種情況下,要尋找絕對中心的位置就簡單多了,判斷方式會變得簡潔一點。

先判斷左右兩側最高點是否一樣高。
 甲、如果不一樣高,上方邊際線就出來了,答案也就出來了。O(1)。
 乙、如果一樣高,則需要判斷上方邊際線的凹凸。
   檢查左右兩側最高點,是不是來自同一點的最短路徑長度,若是則為凸。O(V)。

計算兩點之間最短路徑,只需V次BFS,需時O(VE)。尋找絕對中心,仍需時O(VE)。總時間複雜度降為O(VE)。

UVa 10805

延伸閱讀:點有加權效果的絕對中心

absolute_center(G) = arg min max {d(i, j) ⋅ w(j)}
                      i   i  j∊V

令圖上的點與邊都擁有正權重,距離重新定義為最短路徑乘上端點的權重。在此狀況下,尋找絕對中心,變得要排序,需時O(VElogV)。各位可以想一想怎麼做。