最短路径的特性ppt课件

1、Chapter 25All-Pairs Shortest Path25.1 最短路徑的特性最短路徑的特性 最短路徑的結構：一切最短路徑的子路徑均為最短路徑。 如：(vi,vk,vj)為vi到vj的最短路徑，則(vi,vk)必為vi到vk的最短路徑。 即：(vi,vj)=(vi,vk)+w(vk,vj)最短路徑的特性最短路徑的特性 一個直覺的遞迴解：定義d(m)(i,j)為包含至多m個邊自ij的最短路徑長度。則：),(),(),(min),(,0),()1()1()()0(jkwkidjidjidjijijidmmm利用遞迴解計算出最短路徑利用遞迴解計算出最短路徑 令n=|V|，如一圖無負迴圈，

2、則d(n-1)(i,j)即為ij的最短路徑長度。 可以直覺运用動態規劃的方式來求出解，但耗時O(|V|3log|V|)反不如直接利用Dijkstra演算法直接求出一切點作為起點到其他點的最短路徑(以Linear array實做耗時O(|V|3)。All-pairs Shortest Paths演算法演算法 輸入：一無負迴圈圖G=(V,E)，|V|=n。nn adjacency matrix W=(Wi,j)EvuEvujiwjijiW),( ,),( ,),(,0,All-pairs Shortest Paths演算法演算法 輸出：nn minimum distance matrix D=(D

3、i,j)Di,j=(i,j)nn predecessor matrix =(i,j)假设ij無路徑則i,j=NIL，否則i,j紀錄ij最短路徑上j之前的點ikji,jExtend-Shortest-Paths(D,W) nrowsD Let D = (Di,j) be an nn matrixfor i=1 to n do for j=1 to n do Di,j for k=1 to n doDi,jmin(Di,j,Di,k+Wk,j)return DTime Complexity: O(n3)Slow-All-Pairs-Shortest-Paths(G,W) n|V|D(1)Wfor

4、m=2 to n-1 doD(m)Extend-Shortest-Paths(D(m-1),W)return D(n-1)Time Complexity: O(n4)Faster-All-Pairs-Shortest-Paths(G,W) n|V|D(1)=Wm=1while n-1m do D(2m)Extend-Shortest-Paths(D(m),D(m) m = 2mreturn D(m)Time Complexity: O(n3logn)25.2 Floyd-Warshall演算法演算法 主要利用不同的觀察找出新的遞迴式，使得演算法複雜度降低至O(n3)，在邊數多的時候能有比Dij

5、kstra演算法更迅速的求出一切的最短路徑。 假设一ij的路徑為(i,u1,um,j)，則我們稱u1,um為該路徑的Intermediate vertex(中間點)。Floyd-Warshall演算法演算法 假定點集合V=1,n，定義d(m)(i,j)為中間點僅能够為1,m最短的ij路徑長。故：),(),(),(min),(,),(,0),()1()1()1()()0(jmdmidjidjidjijiwjijidmmmmFloyd-Warshall演算法正確性分析演算法正確性分析 考慮中間點僅能够為1,k。 如k不在ij最短路徑上，則中間點僅能够為1,k-1，故此時：d(k)(i,j)=d(k

6、-1)(i,j)。Floyd-Warshall演算法正確性分析演算法正確性分析 如k在ij最短路徑上，則將ik及kj兩段分開看，這兩個路徑必然不能够有中間點為k，否則按照無負迴圈的假定，ik或kj不是最短路徑，違背最短路徑的性質。故此時： d(k)(i,j)=d(k-1)(i,k)+d(k-1)(k,j)。ikj中間點僅有1,k-1中間點僅有1,k-1Floyd-Warshall演算法演算法Floyd-Warshall(G,W) n|V|D(0)Wfor k = 1 to n do for i = 1 to n do for j = 1 to n do if D(k-1)i,jD(k-1)i,

7、k+D(k-1)k,j then D(k)i,jD(k-1)i,k+D(k-1)k,j i,j k,j else D(k)i,jD(k-1)i,jreturn D(n)Time Complexity: O(n3)建造建造Shortest path 初始化i,j時，如i=j或(i,j) E則初始為NIL，否則初始為i。 等執行完演算法後，則可利用Single-Source shortest path的方式，藉由Predecessor graph來建立出ij的最短路徑。Floyd-Warshall範例範例1253438-4174-526Floyd-Warshall範例範例NILNILNILNILN

8、ILNILNILNILNILNILNILNILNILNILNILNILD544322111 06052047104830)0()0(Floyd-Warshall範例範例NILNILNILNILNILNILNILNILNILNILNILNILNILNILD51414322111 0620552047104830)1()1(Floyd-Warshall範例範例NILNILNILNILNILNILNILNILNILNILNILD51414223221211 06205521150471044830)2()2(Floyd-Warshall範例範例NILNILNILNILNILNILNILNILNILN

9、ILNILD51434223221211 06205121150471044830)3()3(Floyd-Warshall範例範例NILNILNILNILNILD54341434123412441241 0615820512350471140344130)4()4(Floyd-Warshall範例範例NILNILNILNILNILD54341434123412441543 0615820512350471140342310)5()5(25.3 Johnsons algorithm Johnsons演算法可用於計算All pairs shortest path問題。 在邊的數量不多的時候，如|E

10、|=O(|V|log|V|)時，能有比Warshall-Floyd演算法較佳的效能。 其輸入需求是利用Adjacency list表示的圖。Johnsons algorithm Johnsons 演算法利用reweighing來除去負邊，使得該圖可以套用Dijkstra演算法，來達到較高的效能。 Reweighing是將每個點v設定一個高度h(v)，並且調整邊的weight function w(u,v)成為w(u,v)=w(u,v)+h(u)-h(v)。 令(u,v)如此調整之後的最短距離，則原先的最短距離(u,v)=(u,v)-h(u)+h(v)。Johnsons algorithmJoh

11、nson(G) compute G, where VG=VGs and EG=EG(s,v):vVGif Bellman-Ford(G,w,s)=False then print “ a neg-weight cycleelse for each vertex v VG set h(v)=(s,v) computed by Bellman-Ford algo. for each edge (u,v)EG w(u,v)=w(u,v)+h(u)-h(v) for each vertex u VG run Dijkstra(G,w,u) to compute (u,v) for each v VG

12、duv=(u,v)-h(u)+h(v)return DJohnsons algorithm範例範例37428-461-5Johnsons algorithm範例範例37428-461-5s00000参与一個點s，以及自s拉一條weight為0的邊到每一點。Johnsons algorithm範例範例-10-5-4037428-461-5s00000執行Bellman-Ford演算法，得到自s出發每一點的最短距離。Johnsons algorithm範例範例-10-5-4041002130200做完reweightingJohnsons algorithm範例範例2/10/02/-30/-42/041002130200紅線部分是Shortest-paths tree。點的數字a/b代表自出發點(綠色點)出發，到達該點的最短路徑(Reweighting後的圖/原圖)。Johnsons algorithm範例範例0/02/30/-42/-10/141002130200Johnsons algorithm範例範例0/42/70/02/30/541002130200Johnsons algorithm範例範例0/-12/20/-52/-20/041002130200Johnsons algorit