最短路徑

INT(32bits) 範圍 (-2147483648 ~ 2147483647)
- #define INF 1e9 (1000000000)
- INT_MAX (<limits.h>, <climits>)
LONG LONG, INT64 (64bits) 範圍 (-9223372036854775808 ~ 9223372036854775807)
- #define INF (1ll << 60)
- LLONG_MAX (<limits.h>, <climits>)

使用INT_MAX和LLONG_MAX時，要注意溢位問題。

路徑中無限大的意義

如果一條路徑的權重是無限大，並不是代表距離很遠，而是表時起點終點不相連。

鬆弛 (Relaxation)

鬆弛是設計最短路徑演算法中，最重要的操作

目的在於不斷尋找捷徑，將捷徑加入路徑來取代原本的路徑

最短路徑的問題類型

點到點最短路徑 (Point-to-Point Shortest Path)
- 找出起點到終點的最短路徑
單源最短路徑 (Single Source Shortest Paths)
- 找出起點到所有點的最短路徑
全點對最短路徑 (All Pairs Shortest Paths)
- 找出所有點到點的最短路徑

單源最短路徑 (Single Source Shortest Paths)

Bellman-Ford Algorithm

#想法

不斷對所有邊進行鬆弛的操作
共執行|V-1|鬆弛，可以得到一個最短路徑樹

#演算法

記錄所有邊 E={u,v,cost}
令 d[a] 為 s 到 a 的最短路徑權重，初始化 d[s] = 0, d[其他] = Inf
執行以下步驟 |V-1|次
1. 窮舉邊 e={a,b,cost} d[a] + cost < d[b]
2. 以邊a,b來當作a到b的一條捷徑，更新 d[b] = d[a] + cost

#複雜度分析

步驟3執行|V-1|次，窮舉所有邊共|E|個邊

複雜度為 O(|V||E|)

#證明

每次鬆弛操作實際上是對相鄰節點的存取，第n次鬆弛操作保證了所有深度為n的路徑最短。由於圖的最短路徑最長不會經過超過|V|-1條邊，所以可知Bellman-Ford Algorithm 所得為最短路徑。

procedure BellmanFord(list vertices, list edges, vertex source)

// 讀入邊和節點的列表並對distance和predecessor寫入最短路徑

// 初始化圖

for each vertex v in vertices:

if v is source then distance[v] := 0

else distance[v] := infinity

predecessor[v] := null

// 對每一條邊重複操作

for i from 1 to size(vertices)-1:

for each edge (u, v) with weight w in edges:

if distance[u] + w < distance[v]:

distance[v] := distance[u] + w

predecessor[v] := u

// 檢查是否有負權重的迴圈

for each edge (u, v) with weight w in edges:

if distance[u] + w < distance[v]:

error "圖包含具負權重的迴圈"

Dijkstra's algorithm

#想法

不斷找最短的邊拿出來看能不能鬆弛
採用貪心(Greedy)策略

#演算法

以adjacency list紀錄圖
令 d[a] 為 s 到 a 的最短路徑權重，初始化 d[s] = 0, d[其他] = Inf
執行以下步驟直到所有點加入最短路徑樹
1. 找一條離起點最近的點 u 且此點不在最短路徑樹裡面
2. 將 u 加入最短路徑樹
3. 找到 u 相連的所有點 v
  1. 如果 d[u] + cost(u,v) < d[v]，d[v] := d[u] + cost(u,v)
    - (相當於在用 u->v 做鬆弛)

#複雜度分析

步驟2初始化 O(V)
步驟3 共執行V次
步驟3-1 找出最近的點如果使用C++的priority_queue O(log|V|)
步驟3-3 更新點u離起點的距離如果使用C++的priority_queue O(1)
複雜度 O(|E|+|V|log|V|)

1 function Dijkstra(G, w, s)

2 for each vertex v in V[G] // 初始化

3 d[v] := infinity // 將各點的已知最短距離先設成無窮大

4 previous[v] := undefined // 各點的已知最短路徑上的前趨都未知

5 d[s] := 0 // 因為出發點到出發點間不需移動任何距離，所以可以直接將s到s的最小距離設為0

6 S := empty set

7 Q := set of all vertices

8 while Q is not an empty set // Dijkstra演算法主體

9 u := Extract_Min(Q)

10 S.append(u)

11 for each edge outgoing from u as (u,v)

12 if d[v] > d[u] + w(u,v) // 拓展邊（u,v）。w(u,v)為從u到v的路徑長度。

13 d[v] := d[u] + w(u,v) // 更新路徑長度到更小的那個和值。

14 previous[v] := u // 紀錄前趨頂點

比較

Dijsktra's Algorithm 是目前已知的單源最短路最快演算法

但是無法處理負環

相對的 Bellman Ford 雖然比較慢，但是可以找出是否有負環

如果有興趣的話有一種Bellman Ford的改良叫做最短路徑快速演算法（英語：Shortest Path Faster Algorithm (SPFA)）可以加進codebook裡面，不過鮮少用到

全點對最短路徑 (All Pairs Shortest Paths)

Floyd-Warshall algorithm

#想法

窮舉中間點，看看能不能用該中間點使得兩個點之前可以有捷徑
採用動態規劃(Dynamic Programming)的技巧

#演算法

這邊推薦使用adjacency matrix 記錄圖 (令w[u][v] 為 u 到 v 的權重)
令 d[u][v] 為 u 到 v 的最短路徑權重，初始化 for all {u,v} in G: d[u][v] := w[u][v]
窮舉中間點 k from 1 ~ |V|
- 窮舉起點 s from 1 ~ |V|
  - 窮舉終點 t from 1 ~ |V|
    - 如果 d[s][t] > d[s][k] + d[k][t] (經由k來鬆弛)
      - d[s][t] := d[s][k] + d[k][t]

#複雜度分析

步驟3的迴圈總共進行3次1~|V|
複雜度 O(|V|^3)

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)

2 for each vertex v

3 dist[v][v] ← 0

4 for each edge (u,v)

5 dist[u][v] ← w(u,v) // the weight of the edge (u,v)

6 for k from 1 to |V|

7 for i from 1 to |V|

8 for j from 1 to |V|

9 if dist[i][j] > dist[i][k] + dist[k][j]

10 dist[i][j] ← dist[i][k] + dist[k][j]

11 end if

比較

對於邊不多，點很多的題目，容易超出複雜度，這時可以做 V 次單源最短路

V次Dijsktra:

O(|V| * (|E|+|V|log|V|)
O(|V||E|+|V|^2log|V|)

社課練習

uva-558 - Wormholes https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499

uva-10986 - Sending email https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1927

TIOJ 1096 . E.漢米頓的麻煩 https://tioj.ck.tp.edu.tw/problems/1096

Google Sites

Report abuse