《TheShortestPath(最短路径).ppt》由会员分享，可在线阅读，更多相关《TheShortestPath(最短路径).ppt（19页珍藏版）》请在金锄头文库上搜索。
1、最短路徑,The Shortest Path,The Shortest Path(最短路徑),由某節點到其他各個節點之最短路徑。 各個節點之間最短路徑。 最短路徑的定義 : 一條從節點S到節點D最短路徑P，它的總權重最少：,單一起點到其他節點最短路徑,採用貧婪(Greedy)策略 如圖是沒有負權重的網路 設起點為0，求節點0到節點1 最短路徑 節點0到 1，路徑長原為50， 經由節點2，路徑 0 - 2 - 1 ，路徑為45 ，然不滿足， 繼續尋找得到路徑0 - 2 - 3 - 1 ，路徑長40為最短。,Dijkstras演算法則,要找出某一頂點到其他節點的最短路徑，可利用Dijkstras演
2、算法求得。 其過程如下：,D = A F, I ( I =1, N ) S = F V = 1, 2, , N D為N個位置的陣列，用來儲存某一頂點到其他頂點的最短距離，F表示由某一起始點開始，A F, I是表示F點到I點的距離，V是網路中所有頂點的集合，S也是頂點的集合。 從VS集合中找一頂點t，使得D t是最小值，並將t放入S集合，一直到VS是空集合為止。 根據下面的公式調整D陣列中的值： D I = min ( D I, D t +A t, I; (I , t )E) 其中I是指t的相鄰各頂點。 繼續回到(2)執行。,演算法,圖解演算法,若Procedure SHORTEST_PATH
3、(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 ; num2 While num n do Choose u : DIST(u) = minDIST(w) S(u)1 ; numnum+1 For all w with S(w) = 0 do DIST(w) min DIST(w), DIST(u) + COST(u , w ) end end end SHORTEST_PATH,演算虛擬碼,演算程式碼 同樣的，我們可以將D
4、ijkstra演算法，以C語言表達如下： #define N 6 #define MAX_I 10000 int adj_matrix NN int path N, dist N, sN;,dijkstra ( int v) int i , j , m , min , sN ; for ( i = 0 ; i N ; i +) dist i = adj_matrix vi ; s i = 0 ; path i = v ; s v = 1 ;,for ( i = 0 ; i N 2 ; i + ) min = MAX_I ; for ( j = 0 ; j N ; j +) if ( dist
5、j min ,s m = 1 ; for ( j = 0 ; j dist m + adj_matrix mj) dist j = dist m + adj_matrix mj ; path j = m ; ,範例,各節點之最短路徑,前面所探討的是固定一點為起點，而其他節點為終點節點。 任何兩點之間的最短距離(All-pairs shortest paths)，其公式如下： Ak ij = min Ak-1 ij，Ak-1 ikAk-1 kj , k1 A0 ij = length ij 其中k表示經過節點的名稱， Ak ij表示由i到j經由k節點的最短距離。,演算法則,Dijkstra演算法
6、： 依序分別以每一個頂點為起始節點，利用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 )，0kN-1。 因為 Ai(i , j )是節點i至節點j之直通距離。 A(i , j )走節點i至節點j之最短距離，但這條最路徑通過節點的編號不超過0。 Ai(i , j )走節點i至節點j之最短距離，且這條最路徑通過節點的編號不超過k。 因此 只需算出Ak-1(i , j )
7、，便可知任一節點之最短距離。,演算法,圖解 Floyd 演算法,演算虛擬碼 Procedure FLOYD(W) N rowsW D(0) W for k1 to n do for i 1 to n do for j1 to n do end for end for end for return D(n) end FLOYD,演算程式碼 int dist NN ; floyd ( ) int i , j , k ; for ( i = 0 ; i dist I k + dis kj; ,範例,設在註有各地距離之地圖上 求各地間之最短距離。 利用矩陣方式表示。,網路圖,AB是5， AC是6， BA是10， BC是16， CA是3， CB是2。,
