本文正體字版由OpenCC轉換

[次短路徑]

次短路徑可以看作是k短路徑問題的一種特殊情況，求k短路徑有Yen算法等較爲複雜的方法，對於次短路徑，可以有更爲簡易的方法。下面介紹一種求兩個頂點之間次短路徑的解法。

我們要對一個有向賦權圖(無向圖每條邊可以看作兩條相反的有向邊)的頂點S到T之間求次短路徑，首先應求出S的單源最短路徑。遍歷有向圖，標記出可以在最短路徑上的邊，加入集合K。然後枚舉刪除集合K中每條邊，求從S到T的最短路徑，記錄每次求出的路徑長度值，其最小值就是次短路徑的長度。

在這裏我們以爲次短路徑長度可以等於最短路徑長度，如果想等，也可以看作是從S到T有不止一條最短路徑。如果我們規定求從S到T大於最短路徑長度的次短路徑，則答案就是每次刪邊後大於原最短路徑的S到T的最短路徑長度的最小值。

用Dijkstra+堆求單源最短路徑，則每次求最短路徑時間複雜度爲O(Nlog(N+M) + M)，所以總的時間複雜度爲O(NM*log(N+M) + M^2)。該估計是較爲悲觀的，因爲一般來說，在最短路徑上的邊的條數要遠遠小於M，所以實際效果要比預想的好。

[次小生成樹]

類比上述次短路徑求法，很容易想到一個“枚舉刪除最小生成樹上的每條邊，再求最小生成樹”的直觀解法。如果用Prim+堆，每次最小生成樹時間複雜度爲O(Nlog(N+M) + M)，枚舉刪除有O(N)條邊，時間複雜度就是O(N^2log(N+M) + N*M)，當圖很稠密時，接近O(N^3)。這種方法簡易直觀，但我們有一個更簡單，而且效率更高的O(N^2+M)的解法，下面介紹這種方法。

首先求出原圖最小生成樹，記錄權值之和爲MinST。枚舉添加每條不在最小生成樹上的邊(u,v)，加上以後一定會形成一個環。找到環上權值第二大的邊(即除了(u,v)以外的權值最大的邊)，把它刪掉，計算當前生成樹的權值之和。取所有枚舉修改的生成樹權值之和的最小值，就是次小生成樹。

具體實現時，更簡單的方法是從每個節點i遍歷整個最小生成樹，定義F[j]爲從i到j的路徑上最大邊的權值。遍歷圖求出F[j]的值，然後對於添加每條不在最小生成樹中的邊(i,j)，新的生成樹權值之和就是MinST + w(i,j) - F[j]，記錄其最小值，則爲次小生成樹。

該算法的時間複雜度爲O(N^2 + M)。由於只用求一次最小生成樹，可以用最簡單的Prim，時間複雜度爲O(N^2)。算法的瓶頸不在求最小生成樹，而在O(N^2+M)的枚舉加邊修改，所以用更好的最小生成樹算法是沒有必要的。

[次短路徑與次小生成樹的例題]

HAOI 2005 路由選擇問題 直接求次短路徑。

pku 3255 Roadblocks 稍微特殊的次短路徑，允許邊重複走。

Ural 1416 Confidential 求次小生成樹的問題、

pku 1679 The Unique MST 判斷最小生成樹是否唯一。

[參考資料]

• Amber的圖論總結

BYVoid 原創講解，轉載請註明。

上次修改時間 2017-05-22