【演算法】筆記二
Minmum spanning tree
- 在一個無向連通圖中，一個包含所有頂點的樹稱為 spanning tree，若圖裡的連線有權重，則權重總和最小的 spanning tree 就是 Minmum spanning tree。而在一個圖中， MST 可能有好幾個。
- 每個頂點所相鄰權重最小的連線必定包含於 MST 之中。
- 將 MST 中某些點和連線合併後，剩下的樹仍然是合併後所產生之子問題的 MST。
- 由上兩點可知，此問題可使用貪婪演算法，將某些必包含於 MST 的點和連線合併後，在遞迴求剩餘圖的 MST。
- Kruskal 演算法：
找到整個圖中權重最小的連線，將此連線相連的兩點合併，遞迴直到完成。時間複雜度為 O(E logV)。
(必須注意，若兩頂點已合併則之間的連線不可再使用。) - Prim 演算法：
由某一點出發，找相鄰權重最小的連線，將連線兩端合併，遞迴。此演算法可使用 heap 達成，將出發點相鄰連線皆丟入堆疊中，再找出權重最小者，若連線的對面不是已合併的頂點，則將該頂點合併，且加入所有與它相鄰的連線於堆疊中。時間複雜度為 O(E logV)。
Single source shortest path
- 在一個有權重的圖中，找到由某一起點走到途中其餘點的最短路徑。
- 在由起點至【能連接到 v 的所有頂點】的最短距離，加上與 v 相連的邊的權重中，取最小值，即為由起點到點 v 的最短距離。
- Dijkstra 演算法：
一開始將起點到自己的距離設為零，而起點到其餘點的距離設為無限大，之後拜訪目前距離起點最近的點，接著使用該點的連線更新起點與其餘點的最短距離，再由未拜訪的頂點中找出目前距離起點最近的點，拜訪他並進行更新，如此遞迴之，直到所有點皆被拜訪即完成任務。O(E + VlogV)。 - 我們可以證明，在 Dijkstra 演算法中第 k 次迴圈會拜訪到距離起點第 k 近的點。因為途中沒有負權重的邊，第一次必定拜訪離起點最近的點，若假設到第 K-1 個迴圈，上述都是對的，則在第 K 次迴圈時，我們會拜訪當時未拜訪的頂點中距離起點最近的點，而此點是只經由前 K-1 個點所能走到最近的點，因為圖上的權重都是正的，所以此點必為第 K 近的點，因此得證。除此之外我們也可以發現每當一個點被拜訪後，他與起點之距離就不會再改變。
(注意當圖中權重可以小於零時，晚被拜訪的點可以更新先被拜訪的點與起點的距離，這樣一來就會得到錯的答案，在此演算法中，距離近的點要先被拜訪是關鍵所在。) - 若這個問題在有向無環圖 (DAG) 中，則有較容易的方法可解決，只需在初始化之後使用 Topological sort ，之後依此順序進行距離的更新即可得到答案。而此演算法在圖中有負的權重時仍然適用。O(V+E)。
- Bellman-Ford 演算法：
先將起點之距離設為零，再將其餘點之距離設為無限大，之後做 V-1 回的更新，每回皆使用全部的邊以任意順序做更新，之後檢查每一條邊 (u,v)，若是走到 v 的距離比走到 u 的距離加上該邊的權重還要大，也就是說這是個可以用來更新距離的邊，則代表此圖上有權重小於零的 cycle；否則即得到答案。O(V^3)。 - 若是 P 是一條起點到 v 的最短路徑，則我們只要依照順序將 P 中每一條邊更新過就可得到起點到 v 的最短距離。而在一個圖中任一條最短路徑最多只會由 V-1 條邊組成，因此Bellman-ford 演算法必可成功更新每一條最短路徑。
- 我們可以證明，若每一條邊 (u,v) 皆不可用於更新，則圖中任意 cycle 權重皆大於等於零。若 (u,v) 不可用於更新，則他的權重加上走到 u 的距離大於等於走到 v 的距離，也就是說，他的權重大於等於走到 v 的距離減掉走到 u 的距離，也就是說我們將任一個 cycle 的權重加起來會大於等於零。
All pairs shortest path
- 我們可以重複 single source 的方法 V 次以找出任意兩點間的最短距離。
- 在一個沒有負權重 cycle 的圖中，任意兩點的最短距離最多只會經過 V-1 條邊。而 u 至 v 的最短距離，會等於 u 到 k 的最短距離加上 k 到 v 的最短距離的最小值，其中 k 為任意頂點。
- 因此我們可以利用動態規劃，將兩點間最多經過 m 條邊的最短距離製成一張表，只要找出 m = V-1 的表便完成任務。
我們可以發現 graph 本身的 adjacency matrix 便是兩點間最多只經過一條邊的最短距離，利用此表便可找出兩點間最多只走兩條邊的最短距離：觀察可得，起點的橫排和終點的直列相加後取最小的項，便是新表格中起點到終點的最短距離。依此將最多走 n 邊的表格與最多走 m 邊的表格做運算，便可得最多走 n+m 邊的表格。因此我們只需做 O(logV) 次表格運算，而每次表格運算花費 O(V^3)，因此時間複雜度為O(lgV*V^3)。 - Floyd-Warshall 演算法：
不同於上一個演算法使用經過邊的數量來做動態規劃，此演算法利用經過的中間點。在限制中間點只能經過 1 至 k 的情況下，兩點間最短路徑要嘛經過 k、要嘛不經過 k ，若是不經過 k ，則與限制中間點為 1 至 k-1 的情況下相同，而若是經過 k，便可將路徑分成由起點到 k 、與由 k 到終點兩部分，而兩子路徑中間點皆受限於 1 至 k-1 之中。由此可見，我們可以藉由動態規劃，由 adjacency matrix (即不經過任何中間點的兩點間最短路徑。) 求出不限制中間點時的兩點間最短距離。
計算中間點限制於 1 至 k 之最短距離時，只需於中間點受限於 1 至 k-1 的表格中，找出原起點至終點的距離，與起點至 k 加上 k 至終點之距離之間的最小值即可。可以簡化成：第 k 行及第 k 列對應至該格之值相加、與那一個格之間的最小值。
可以發現，在此演算法中計算一格的最短距離只需比較兩次，因此總共時間複雜度只需 O(V^3)。 - 為了得到確實路徑，我們建立另外的表以紀錄兩點間最短路徑中的最後一個中間點，查閱此表便可得到整個路徑。而此表一樣可由依序放寬限制中間點的方法得來，若中間點為 1 至 k 表中距離沒有更新，則最後中間點也不必更新；若距離更新，則最後中間點更新為：中間點為 1 至 k-1 表中，k 至終點的最後中間點。
- 利用此演算法，可找到 transitive closure。transitive closure 即將有 path 相連的兩點皆用 edge 相連後的圖。
- 以上演算法皆僅適用於圖中無負權重 cycle 之情況，若有這種情況時則可以使用 Bellman-Ford 演算法做 V 次，或是使用 Johnson 之演算法。
- Johnson 演算法：
重新分配每條邊的權重，使得權重都是正的，且最短路徑不會因此改變，如此便可以使用 Dijkstra 的演算法。做法為將每一個頂點 v 分配一個值 h(v)，令 (u,v) 的新權重為：舊權重加上 h(u) - h(v)。如此一來兩點間的不同路徑的權重改變量會一樣，因此能保有最短路徑；而 cycle 的權重則是新舊相同，因此可檢測出負權重的 cycle。
h(v) 的分配方法如下，將原圖加上一個頂點 s，並與所有頂點相連，權重皆設為零，再使用 Bellman-Ford 計算各點與 s 的最短距離，所得 s 到 v 的最短距離即 h(v)，由 h(v) 的構造方式可發現，每條邊的新權重必大於零。
分配好新權重後，再使用 Dijkstra 演算法對每個頂點作用，再將所得答案減掉改變的量，變回舊權重，即可得到答案。O(V^2lgV+VE)。
留言
張貼留言