k Shortest Walk

給定起點與終點，排名第k短的途徑。有可能跟最短途徑一樣長。或許可以翻譯為「第k短途徑」。

可以直接套用先前所學的Dijkstra's Algorithm，把DP表格開大一點，每個點都儲存前k短的長度，就能解決問題。時間複雜度為O(K * (E+VlogV))。

UVa 10740

k Shortest Path與k Shortest Trail

「第k短路徑」、「第k短跡」尚無有效率的演算法，大多是使用窮舉法，窮舉所有可能的路徑。時間複雜度本是指數時間，但如果配合了heuristic function，理想狀態之下，時間複雜度得宣稱是多項式時間。

主要的演算法有Yen's Algorithm與MPS Algorithm兩個。

http://imlazy.ycool.com/post.1956603.html

http://code.google.com/p/k-shortest-paths/

http://www.mat.uc.pt/~eqvm/OPP/KSPP/KSPP.html

http://blog.csdn.net/sharpdew/archive/2005/08/05/446510.aspx

ICPC 3624

Strictly Second Shortest Walk

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

【註：以下假設有向圖上沒有負環、無向圖上沒有負邊，此時最短途徑恰等於最短路徑。至於有向圖上有負環、無向圖上有負邊的嚴格次短途徑，至今仍無人討論過。】

既然不想走這條路，就必須改走別條路。這是人之常情。

不想找到一條最短路徑，而想找到一條嚴格次短途徑，一種方式是觀察最短路徑的替代道路。

列出所有最短路徑，也就是「最短路徑圖」，從中尋找替代道路。由於替代道路太長，不利分析，於是發揮Incremental Method化整為零的精神：不觀察替代道路的所有邊，改為觀察替代道路上的一條邊。此精神先前也於Label Correcting Algorithm出現過。

【註：一張圖上，給定起點與終點，描出所有最短路徑，此處暫且稱之「最短路徑圖」。此概念尚未出現專有名詞。圖上只有正邊時，最短路徑圖是一張有向無環圖DAG；圖上有零邊或負邊，但是無負環時，最短路徑圖可能會額外出現零環。】

在有向圖上，替代邊必然是最短路徑以外的邊；在無向圖上，替代邊不僅可以採用最短路徑以外的邊，也可以逆行最短路徑上面的邊。替代邊設定為有向邊是比較完善的。

也就是說，嚴格次短途徑一定經過「最短路徑圖」以外的邊；若在無向圖上，也可以經過「最短路徑圖」上的反方向邊。

嚴格次短途徑仍是越短越好。當有一條途徑經過替代邊ij，要使此途徑盡量短，唯一的方法就是：從起點到i必須是最短路徑，從j到終點也必須是最短路徑。接著只要使用窮舉法，窮舉所有可能的替代邊，即可找到其中一條嚴格次短途徑。

一、預先計算起點s出發的單源最短路徑。
二、預先計算抵達終點t的單源最短路徑。
三、窮舉圖上每一條邊ij作為替代邊（無向圖則視作雙向都有邊）：
　甲、取得s->i的最短路徑。
　乙、取得j->t的最短路徑。
　丙、串成一條途徑s->i->j->t。
　　子、若s->i->j->t是最短路徑，表示邊ij不是替代邊，則捨棄之。
　　丑、若s->i->j->t不是最短路徑，就有可能是嚴格次短途徑，則紀錄之。
四、於丑，當中最短的途徑，便是嚴格次短途徑。

窮舉所有邊的過程，其時間複雜度為O(E)，必然小於單源最短路徑的時間複雜度。因此可以直接宣稱時間複雜度等同求單源最短路徑的時間複雜度。

UVa 10342

Next-to-Shortest Path（Strictly Second Shortest Path）

給定起點與終點，「嚴格次短路徑」是權重不等於最短路徑、權重盡量小的路徑。

有向圖　正零負權重　NP-Complete　　光是最短路徑就已經是 NP-complete
　　　　正零權重　　NP-Complete　　1997 美國
　　　　正權重　　　?          　　open problem

無向圖　正零負權重　NP-Complete　　光是最短路徑就已經是 NP-complete
　　　　正零權重　　P          　　O(V^6)      2011 日本
　　　　正權重　　　P          　　O(最短路徑) 2010 台灣

正權重無向圖的演算法，時間複雜度宣稱是O(E+VlogV)。

建立「最短路徑圖」，採用Divide and Conquer，將嚴格次短路徑分為「經過最短路徑圖以外的邊」與「經過最短路徑圖的反方向邊」兩種。這兩種情形分別被以下兩篇論文解決：

Kuo-Hua Kao, Jou-Ming Chang, Yue-Li Wang, Justie Su-Tzu Juan. A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs. Algorithmica, 2010.

Bang-Ye Wu. A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem. Combinatorial Optimization and Applications, 2010.

關鍵點在於把vertex-disjoint paths與dominator兩個概念連結在一起。

【待補文字】

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

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

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

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

直徑和半徑都是最短路徑。根據最短路徑的性質，直徑和半徑中間截一段路徑下來，也都會是最短路徑。

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

int d[10][10]; // adjacency matrix int ecc[10]; // 各點的偏心距 void diameter_radius() { // Floyd-Warshall Algorithm for (int k=0; k<10; ++k) for (int i=0; i<10; ++i) for (int j=0; j<10; ++j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); // 計算偏心距 memset(ecc, 0x7f, sizeof(ecc)); for (int i=0; i<10; ++i) for (int j=0; j<10; ++j) ecc[i] = min(ecc[i], d[i][j]); // 計算直徑和半徑 int diameter = 0; int radius = 1e9; for (int i=0; i<10; ++i) { diameter = max(diameter, ecc[i]); radius = min(radius , ecc[i]); } /* // 直徑也可以這樣算 for (int i=0; i<10; ++i) for (int j=0; j<10; ++j) diameter = max(diameter, d[i][j]); */ }

延伸閱讀：樹的直徑與半徑

樹的直徑與半徑可以利用DFS求得，詳情請看本站文件「Tree」。

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^4)。無負邊，則執行V次Dijkstra's Algorithm，以Fibonacci Heap實作，需時O(V * (E + VlogV))。

二、尋找絕對中心：圖的資料結構是adjacency lists，需時O(VE)。

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

實作

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

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

const int V = 10; int w[V][V]; // adjacency matrix bool visit[V]; // visit record int d[V][V]; // 所有兩點之間最短路徑長度 int rank[V][V]; // 各起點的最短路徑長度順序 void Dijkstra(int s) { int* ds = d[s]; // alias int* rs = rank[s]; for (int i=0; i<V; ++i) visit[i] = false; for (int i=0; i<V; ++i) ds[i] = 1e9; ds[s] = 0; for (int k=0; k<V; ++k) { int i = -1, min = 1e9; for (int x=0; x<V; ++x) if (!visit[x] && ds[x] < min) min = ds[i = x]; if (i == -1) break; visit[i] = true; rs[k] = i; // 順便紀錄各點的最短距離長度順序 for (int j=0; j<V; ++j) if (!visit[j] && ds[i] + w[i][j] < ds[j]) ds[j] = ds[i] + w[i][j]; } } void Kariv_Hakimi() { for (int i=0; i<N; ++i) Dijkstra(i); // 絕對中心的偏心距可能會出現0.5的小數， // 故可直接紀錄兩倍的偏心距。 int ecc2 = 1e9; for (int i=0; i<V; ++i) for (int j=i+1; j<V; ++j) { if (w[i][j] == 1e9) continue; // 如果絕對中心在i點 ecc2 = min(ecc2, d[i][rank[i][V-1]] * 2); // 如果絕對中心在j點 ecc2 = min(ecc2, d[j][rank[j][V-1]] * 2); int* r = rank[i]; // alias // 靠i側時，令a線是目前最高，令b線比a線低並且越來越低。 for (int a=V-1, b=V-2; b>=0; --b) // 靠j側時，b線比a線高，故兩線相交，產生凹處。 if (d[j][r[b]] > d[j][r[a]]) { ecc2 = min(ecc2, d[i][r[b]] + d[i][j] + d[j][r[a]]); a = b; } } cout << "離最遠的點的距離" << double(ecc) / 2.0; }

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

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

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

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

const int V = 10; int adj[V][V], size[V]; // adjacency lists int q[V][V], *qf, *qb; // 10 BFS queues bool visit[V]; // BFS visit record int d[V][V]; // 所有兩點之間最短路徑長度 void BFS(int s) { memset(visit, false, sizeof(visit)); qf = qb = q[s]; visit[s] = true; *qb++ = s; d[s][s] = 0; while (qf < qb) { int i = *qf++; for (int n=0; n<size[i]; ++n) { int j = adj[i][n]; if (!visit[j]) { visit[j] = true; *qb++ = j; d[s][j] = d[s][i] + 1; } } } } void Kariv_Hakimi() { for (int i=0; i<V; ++i) BFS(i); int ecc2 = 1e9; for (int i=0; i<V; ++i) for (int n=0; n<size[i]; ++n) { int j = adj[i][n]; if (j <= i) continue; int ecci = d[i][q[i][V-1]]; int eccj = d[j][q[j][V-1]]; int diff = 1; if (ecci == eccj) for (int k=0; k<V; ++k) if (d[i][k] == ecci && d[j][k] == ecci) { diff = 0; break; } ecc2 = min(ecc2, ecci + eccj - diff); } cout << "離最遠的點的距離" << double(ecc) / 2.0; }

UVa 10805

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

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

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