圖論(二)—最短路徑及網路問題
最短路徑法(Shortest path algorithm)
 觀察:如果s,v1,v2,...,vi,..,vk是s到vk的最短路徑,則s,v1,v2,...,vi是s到vi的最短路徑。
 有四種狀況:
1. 所有的權重均為1。求s到其他所有點之最短路徑。
2. 所有的權重均為非負值(0或大於0)。求s到其他所有點之最短路徑。
3. 權重可以為負,但迴路之總權重不為負值。求s到其他所有點之最短路徑。
4. 任意二點之間的最短路徑。
 第一種情形(所有的權重均為1。求s到其他所有點之最短路徑。)
BFS (Breadth First Search), 複雜度:O(|E|)
Begin
Lable s with 0;
i &#61612
0;
if an unlabeled node adjacent to a node labeled i then
begin
while an unlabeled node adjacent to a node labeled i do
begin
label this node i+1;
end_of_while;
i &#61612
i+1;
go_to if_statement;
end_of_if;
end.
 第二種情形(所有的權重均為非負值,0或大於0。求s到其他所有點之最短路徑。)
Dijstra’s algorithm 複雜度:O(|V|2)
notation: (x)0, label x with 0
Begin
(s) &#61612
0;
(v) &#61612
, vs
/* &#61559
代表無限大 */
T &#61612
V
P &#61612
;
u &#61612
s;
Repeat
for each vertex vT adjacent to u do (v) &#61612
min{(v), (u)+w(u,v)};
T &#61612
T – {u};
P &#61612
P{u};
u &#61612
a new vertex in T with min. (u)
Until either (T = &#61638
or ((u)= &#61559
;
end.
 第三種情形(權重可以為負,但迴路之總權重不為負值。求s到其他所有點之最短路徑。)
Bellman and Ford algorithm 複雜度:O(|V|•|E|)
Umj = the length of a shortest path from s to j among all paths that contain at most m arcs.
=
Begin
m &#61612
0;
U0s &#61612
0;
U0j &#61612
, for all js
/* 代表無限大 */
repeat
m &#61612
m+1;
UmjUjm-1, j, 1 &#61603
j &#61603
n;
for each arc(K,j) in G do
Umj = min{Ujm , UKm-1+w(K,j)};
until (Umj = Ujm-1) or (m = n) for jG;
IF (m = n) and (UmjUjm-1) then output(“exist negative cycle!”)
end.
(例)
令Um = [Umj], j=1,2,3,4
U0 = [0, , , ] /* &#61559
代表無限大 */
U1 = [0, , 4, 10]
U2 = [0, 13, 4, 10] /* 13 = min(13,14) */
U3 = [0, 13, 4, 10]
 第四種情形(任意二點之間的最短路徑)
Floyd and Warshall algorithm 複雜度: O(N3)
Let the vertices be noted by 1,2,3...,n
Uki,j = 介於i,j之間的點編號最高為k時之總長度
Begin
U0ii &#61612
0, i
U0ij &#61612
w(i,j), (i,j)E
U0ij &#61612
, (i,j)E /* &#61559
代表無限大 */
for k=1 to n do
begin
for i=1 to n do
for j=1 to n do
Ukij &#61612
min{Uijk-1, Uikk-1+ Ukjk-1}
end
end
end.
(例)
網路(network)
【定義】
網路(network)是一「加權有向圖」(weighted directed graph),並具有以下之性質:
1. 網路上有二個特殊的點,分別稱之為「源點」(source)和「終點」(sink)。無任何連線(directed link/edge)指向源點;亦無任何連線由終點指向其它節點。源點可以提供無限大的流出量,終點可以容納無限大的流入量。
2. 每一個有向連線均有二個(屬性)權重:「容量」(capacity)與「流量」(flow)。一般而言,容量與流量均是非負數,且容量大於等於流量。
3. 各節點之總流入量等於總流出量(亦即,各節點無存量)。
網路流量問題(Network Flow Problem)
給予一個網路,求取由源點到終點的最大可能流量及路徑。
 求解「網路流量問題」,必須用到「最大流量等於最小切割定理」(max-flow min-cut theorem)。其演算法稱之為Ford &
Fulkerson algorithm。
 Max-flow Min-cut theorem
For any network N, the maximum flow value is equal to the minimum capacity of an s-t cut.
 the labeling algorithm (Ford &
Fulkerson algorithm)
Begin
f(i,j) &#61612
0, (i,j) E
/*any feasible flow = 0 */
(s) &#61612
(-,&#61559
/* assign the initial label to s , where &#61559
represents infinity*/
repeat
/* search for an augmenting path
initially, s is the only vertex that is labeled but unscanned. */
while there is a labeled but unscanned node i do
begin /*scanning i */
for each unlabeled j such that f(i,j) < c(i,j) do
/* forward labeling from i */
&#61540;j &#61612
c(i,j) – f(i,j);
&#61548;(j) &#61612
(i+,&#61540;j);
for each unlabeled j such that f(j,i)>0 do
/* reverse labeling from i */
&#61540;j &#61612
f(j,i);
&#61548;(j) &#61612
(i-,&#61540;j);
mark i “scanned”;
end_of_while;
if t is labeled then do /* flow augmentation */
begin
&#61540
&#61612
min{&#61540;j | j&#61646;V(G) };
increase or decrease a flow of &#61540
units along each arc of the augmenting path according to +, - sign;
erase all scanning mark;
erase all labels except &#61548;(s);
end;
until you are not able to label t;
identify the minimum cut
/* edges from labeled nodes to unlabeled nodes */
end.