所有結(jié)點(diǎn)對(duì)的最短路徑問(wèn)題
Floyd算法
- 前提條件: 可以有負(fù)權(quán)重邊, 但是不能有負(fù)權(quán)重的環(huán).
- 特點(diǎn): 動(dòng)態(tài)規(guī)劃, V^3.
- 按照動(dòng)態(tài)規(guī)劃的步驟:
- 最優(yōu)子結(jié)構(gòu): d[i][j]表示結(jié)點(diǎn)vi至結(jié)點(diǎn)vj的最短路徑, 而帶上了上標(biāo)d[i][j]<k>表示允許取用v1~vk情況下結(jié)點(diǎn)vi至vj的最短路徑. 我們可以看出這里存在了一個(gè)最優(yōu)子結(jié)構(gòu), 因?yàn)槿∮?k的最短路徑是在取用1k-1的最短路徑和用上k的最短路徑之間選取的min.
- 遞歸式: d[i][j]<k> = min{ d[i][j]<k-1>, (d[i][k]<k-1>+d[k][j]<k-1>) }. (常規(guī)情況, 當(dāng)k>=1時(shí))
或者 = w(i, j); (邊界情況, 當(dāng)k=0時(shí)) //其中i=j時(shí), 應(yīng)該w(i, i) = 0; 沒(méi)有(i, j)邊的時(shí)候, 為INF; - 自底向上計(jì)算:
- 三個(gè)循環(huán), i, j, k. k循環(huán)是用來(lái)算d[i][j]這個(gè)格子的min, 總共是一個(gè)二維矩陣, 因此要算O(V^3)時(shí)間.
Floyd(W) { //W[V][V]是二維數(shù)組, 存放邊的權(quán)重.
let D[V][V] be a new array, and D = W;
for k = 1~V:
for i = 1~V:
for j = 1~V:
D[i][j] = min{ D[i][j], D[i][k]+D[k][j] };
return D;
}
用于稀疏圖的Johnson算法
前提條件: 允許有負(fù)權(quán)重的環(huán);
特點(diǎn): 利用G', h(v) = δ(s, v)來(lái)為Dijkstra創(chuàng)造無(wú)負(fù)權(quán)重邊的條件;
Johnson(G, w) {
compute G':
G'.V = G.V ∪ {s};
G'.E = G.E ∪ {(s, v) for all v ∈ G.V}
w(s, v) = 0 for all v ∈ G.V
if Bellman-Ford(G', w, s) == FALSE: {
print "The graph contains negative loop;"
}
else: {
for each v ∈ G'.V:
set h(v) = δ(s, v) from Bellman-Ford
for each edge(u, v)∈G'.E:
set w'(u, v) = w(u, v) + h(u) - h(v) //set all weight to non-negative.
let D = d[][] be n*n matrix
for each u∈G.V:
do Dijkstra(G, w', u)
for each v∈G.V:
d[u][v] = δ'(u, v) + h(v) - h(u)
return D matrix
}
}
算法時(shí)間復(fù)雜度分析:
Bellman-Ford已知是O(VE) 因?yàn)橛蠽-1輪對(duì)所有邊的操作, Dijkstra是O(ElgV)或者O(VlgV+E), 因?yàn)閑xtract-min有V次, decrease-key有E次.
本算法主要時(shí)間顯然是花在了對(duì)所有點(diǎn)進(jìn)行Dijkstra操作, 顯然總時(shí)間是O(VElgV) 或者 O(V^2*lgV+VE).
最大流問(wèn)題
基本方法
Ford-Fulkerson method
Ford-Fulkerson-Method(G, s, t)
initiate flow f to 0
while there exists an augmenting path p in residual network Gf:
augment flow f along p
return f
定理
最大流最小割定理
定理: f是G的一個(gè)最大流
= 殘存網(wǎng)絡(luò)Gf不再包含任何增廣路徑
= |f| = c(S, T) , 其中(S, T)是流網(wǎng)絡(luò)G的某個(gè)切割;
- 說(shuō)明: 第三行某個(gè)切割可以是任意一個(gè)切割, 因?yàn)榱骶W(wǎng)絡(luò)具有切割流量相等的性質(zhì).
基本款算法
Ford Fulkerson Basic
/* 基本的FF最大流算法 */
// 約定: (u,v).f代表邊(u,v)上當(dāng)前的流量;
// Cf(p)代表path p整條最短路徑所允許的殘余網(wǎng)絡(luò)最大流量
// Cf(u, v)代表(u, v)邊上的殘余網(wǎng)絡(luò)流量, 本質(zhì)上是一種潛能(potential)
Ford-Fulkerson(G, s, t)
for each edge (u, v)∈G.E:
(u, v).f = 0
while there exists an augmenting path p in residual network Gf:
Cf(p) = min{Cf(u, v): (u,v) is in path p}
for each edge(u, v) in path p:
if (u, v) ∈ G.E:
(u, v).f = (u, v).f + Cf(p)
else:
(v, u).f = (v, u).f - Cf(p)
- 找augmenting path的方法: 用BFS對(duì)殘存網(wǎng)絡(luò)Gf進(jìn)行搜索, 找到一條path;
時(shí)間復(fù)雜度分析: 算法初始化花費(fèi)Θ(E), 而while循環(huán)的條件如果是用廣度優(yōu)先搜索, 每次要花O(V+E) = O(E), 而循環(huán)內(nèi)求殘余容量Cf(p)操作最多有|V-1|條邊構(gòu)成一條最短路徑, 因此是O(V), 而接下去對(duì)path上所有邊的操作, 也是O(V)的. 因?yàn)閂<=E, 因此單次while循環(huán)消耗O(E), 而由我們的關(guān)鍵邊上限定理, 可以知道最多有VE條關(guān)鍵邊, 每條path至少一條關(guān)鍵邊, 因此有O(VE)條path, 因此總時(shí)間復(fù)雜度為O(V·E^2).
算法的正確性:
為什么使用BFS不斷找出最短邊(所有邊長(zhǎng)度設(shè)定為1), 可以實(shí)現(xiàn)把while循環(huán)控制在VE次呢?
先介紹一個(gè)基礎(chǔ): δ(s, v)單調(diào)遞增定理
從源點(diǎn)s到非終點(diǎn)t的某個(gè)點(diǎn)v的最短距離總是在遞增, 即δ'(s, v) >= δ(s, v). 證明:
反證法: 假設(shè)某輪增加流量之后, 存在δ'(s, v)<δ(s, v). 這時(shí), 我們找處于邊界v點(diǎn), 從s到v點(diǎn)的最短路徑上, v前面一個(gè)點(diǎn)u滿足δ'(s, u)=δ(s, u). 已知δ(s, v) <= δ(s, u)+1, δ'(s, u)<=δ'(s, v)+1, δ'(s, v)<=δ(s, v)-1, 那么δ(s, u)+1 >= δ'(s, v)-1, 也就是δ(s, u) >= δ'(s, v)-2與δ'(s, u)<=δ'(s, v)+1是矛盾的.
更加直覺(jué)一些地, 隨著算法運(yùn)行, 有些邊可能由于流量被加到滿導(dǎo)致在殘存網(wǎng)絡(luò)中消失:
- 如果消失的邊在s~v的最短路徑上, 顯然δ(s, v)將不得不繞別的路, 因而會(huì)增加;
- 如果消失的邊不在s~v的最短路徑上, 那么也不會(huì)影響到δ(s, v).
- 要認(rèn)識(shí)到, 只有當(dāng)圖中出現(xiàn)了連接之前從未被連接過(guò)的兩點(diǎn)的新邊, 才存在使δ(s, v)下降的可能性.
關(guān)鍵邊O(VE)上界的推導(dǎo):
(u, v)如果第一次被當(dāng)做最短路徑p的關(guān)鍵邊話, 會(huì)從Gf殘存網(wǎng)絡(luò)圖上消失, 此時(shí)有δ(s, v) = δ(s, u)+1;
其如果想再次成為關(guān)鍵邊, 至少要滿足必要條件 (v, u).f 被增加過(guò), 且(u, v)再次被當(dāng)成最短路徑的一部分. (v, u).f要被增加過(guò)的話, 那么(v, u)邊得被納入過(guò)最短路徑, 那么(v, u)滿足了δ'(s, u) = δ'(s, v)+1;
已知定理26.7說(shuō)殘存網(wǎng)絡(luò)中δ(s, v)隨著每次流量的遞增操作而單調(diào)遞增 ==> δ'(s, v) >= δ'(s, v), 所以δ'(s, u) = δ'(s, v)+1>=δ(s, v)+1 = δ(s, u)+2.
因此我們得到了一個(gè)性質(zhì): 當(dāng)(u, v)邊成為一次關(guān)鍵邊后, δ(s, u) = δ(s, u)+2, 即關(guān)鍵邊遞增, 遞增的步長(zhǎng)為2.
已知從起點(diǎn)s到終點(diǎn)t最短路徑最長(zhǎng)不能超過(guò)V-1, u除了不可能是終點(diǎn)t外, 可以是任何點(diǎn), 因此(u, v)最多可以當(dāng)關(guān)鍵邊(V-2)/2次, 從而每條邊只能當(dāng)關(guān)鍵邊次數(shù) = O(V/2) = O(V), 那么對(duì)所有邊來(lái)說(shuō), 最多只能有O(VE)次關(guān)鍵邊的出現(xiàn).
延伸: O(VE)條關(guān)鍵邊, 而每個(gè)增廣路徑至少有一條關(guān)鍵邊, 因此O(VE)條增廣路徑.
