最短路徑 The Shortest Path.

Presentation on theme: "最短路徑 The Shortest Path."— Presentation transcript:

1 最短路徑 The Shortest Path

2 The Shortest Path(最短路徑)
由某節點到其他各個節點之最短路徑。 各個節點之間最短路徑。 最短路徑的定義 : 一條從節點S到節點D最短路徑P，它的總權重最少：

3 單一起點到其他節點最短路徑 採用貧婪(Greedy)策略 如圖是沒有負權重的網路 設起點為0，求節點0到節點1 最短路徑
節點0到 1，路徑長原為50， 經由節點2，路徑 0 -> 2 -> 1 ，路徑為45 ，然不滿足， 繼續尋找得到路徑0 -> 2 -> 3 -> 1 ，路徑長40為最短。

4 Dijkstra’s演算法則 要找出某一頂點到其他節點的最短路徑，可利用Dijkstra’s演算法求得。 其過程如下：

5 D = A [F, I] ( I =1, N ) S = {F} V = {1, 2, … , N} D為N個位置的陣列，用來儲存某一頂點到其他頂點的最短距離，F表示由某一起始點開始，A [F, I]是表示F點到I點的距離，V是網路中所有頂點的集合，S也是頂點的集合。 從V－S集合中找一頂點t，使得D [t]是最小值，並將t放入S集合，一直到V－S是空集合為止。 根據下面的公式調整D陣列中的值： D [I] = min ( D [I], D [t] +A [t, I; ] ((I , t )E) 其中I是指t的相鄰各頂點。 繼續回到(2)執行。

6 演算法 ＝＞圖解演算法

7 ＝＞演算虛擬碼 若Procedure SHORTEST_PATH (v, COST, DIST, n) Declare S (1 : n )
for j ← 1 to n S( j )← 0 ; DIST( j )←COST( v , j ) End S( v )←1 ; DIST( v )←0 ; num←2 While num < n do Choose u : DIST(u) = min{DIST(w)} S(u)←1 ; num←num+1 For all w with S(w) = 0 do DIST(w) ←min {DIST(w), DIST(u) + COST(u , w ) } end end SHORTEST_PATH

8 ＝＞演算程式碼 同樣的，我們可以將Dijkstra演算法，以C語言表達如下： #define N 6 #define MAX_I 10000
int adj_matrix [N][N] int path [N], dist [N], s[N];

9 dijkstra ( int v) { int i , j , m , min , s[N] ; for ( i = 0 ; i < N ; i ++) dist [i] = adj_matrix [v][i] ; s [i] = 0 ; path [i] = v ; } s [v] = 1 ;

10 for ( i = 0 ; i < N – 2 ; i ++ ) min = MAX_I ; for ( j = 0 ; j < N ; j ++) if ( dist [j] < min && s [j] = = 0) { min = dist [j] ; m = j ; }

11 s [m] = 1 ; for ( j = 0 ; j < N ; j ++) { if ( dist [j] > dist [m] + adj_matrix [m][j]) dist [j] = dist [m] + adj_matrix [m][j] ; path [j] = m ; }

12 範例 Iteration S Vertex Selected DIST Initial 1 2 3 4 5 6 5,6 5,6,7
5,6,7,4 5,6,7,4,8 5,6,7,4,8,3 5,6,7,4,8,3,2 － 7 8 ∞ 3350 3250 2450 1500 1250 250 1150 1650

13 各節點之最短路徑 前面所探討的是固定一點為起點，而其他節點為終點節點。
任何兩點之間的最短距離(All-pairs shortest paths)，其公式如下： Ak [i][j] = min { Ak-1 [i][j]，Ak-1 [i][k]＋Ak-1 [k][j] } , k≧1 A0 [i][j] = length [i][j] 其中k表示經過節點的名稱， Ak [i][j]表示由i到j經由k節點的最短距離。

14 演算法則 Dijkstra演算法： 依序分別以每一個頂點為起始節點，利用Dijkstra演算法即可獲得任一節點的最短路徑和距離。
Floyd演算法：假設節點編號為0、1、2、...、N-1， 並且令Ai-1(i , j )=Length(i , j)， 並求出Ai(i , j )，Ai(i , j )＝min{ Ai-1(i , k)＋Ai-1(k , j )}，0≦k≦N-1。 因為 Ai(i , j )是節點i至節點j之直通距離。 A０(i , j )走節點i至節點j之最短距離，但這條最路徑通過節點的編號不超過0。 Ai(i , j )走節點i至節點j之最短距離，且這條最路徑通過節點的編號不超過k。 因此 只需算出Ak-1(i , j )，便可知任一節點之最短距離。

15 演算法 ＝＞圖解 Floyd 演算法 起始矩陣A-1：
A-1[i][j] = length [i][j]表示由i到j的最短距離，其間不經由任何節點。 矩陣A0： A0[i][j]由i到j，經由節點０的最短距離；其中2→1的距離已由∞更新成7。 矩陣A1： A1[i][j]由i到j，經由節點1的最短距離；其中0→2的距離已由11更新成6。 矩陣A2： A2[i][j]由i到j，經由節點2的最短距離；其中1→0的距離已由6更新成5。

16 ＝＞演算虛擬碼 Procedure FLOYD(W) N ←rows[W] D(0) ←W for k←1 to n do
for i ←1 to n do for j←1 to n do end for return D(n) end FLOYD

17 ＝＞演算程式碼 int dist [N][N] ; floyd ( ) { int i , j , k ;
for ( i = 0 ; i < N; i ++) for (j = 0 ; j < N ; j ++) for (k = 0 ; k < N ; k ++) if ( dist [i] [j] > dist [I ][k] + dis [k][j]; }

18 範例 設在註有各地距離之地圖上 求各地間之最短距離。 利用矩陣方式表示。 A B C 3 10 2 6 5 網路圖

19 A→B是5， A→C是6， B→A是10， B→C是16， C→A是3， C→B是2。