single-sourceshortestpaths.ppt

Single-Source Shortest Paths Single-Source Shortest Paths Shortest-path problem 即是在一圖上找出兩點間最短路徑。 G=(V,E)是一個Weighted Directed Graph(加權有向圖)透過Weight function w: E?R界定出每個邊的權重。 以p=(v0,v1,…,vk)表一個自v0到vk的Path(路徑)。 Shortest-path problem 定義 定義自u到v的最短距離 Shortest-path tree rooted at s 對應於圖G=(V,E)的Shortest-path tree rooted at s (根於s之最短路徑樹) G’=(V’,E’)，滿足下列三點： V’是s可達的點集合。 G’是一個以s為根的Rooted Tree。 在G’中s到v的simple path即為G中s到v的最短路徑。 Shortest-path tree rooted at s範例 Predecessor graph 對一圖G=(V,E)，根據一個表π來建構的子圖Gπ=(Vπ,Eπ)，滿足以下條件： π[s]=NIL，且s∈Vπ。 若π[v]≠NIL則(π[v],v)∈Eπ且v∈Vπ 。 Shortest-path tree rooted at s是Predecessor graph的特例。 Predecessor graph範例 Initialize-Single-Source演算法 定義變數d[v]代表目前已知之自s至v的最短距離。 定義變數π[v]代表目前已知自s至v的最短路徑上，v之前的那一點。 初始時，d[v]=∞，π[v]=NIL，d[s]=0。即除自s到s的最短路徑已知之外，其餘均設為未知。 Initialize-Single-Source演算法 Initialize-Single-Source(G,s) { for each vertex v∈V[G] do d[v]?∞ π[v]?NIL d[s]?0 } Relaxation 演算法 主要的目的在於利用邊(u,v)的資訊來更新目前所知的最短路徑。 Relax(u,v,w) { if d[v]d[u]+w(u,v) then d[v]?d[u]+w(u,v) π[v]?u } Relaxation 範例 最短路徑與Relaxation的性質 三角不等式：對所有的邊(u,v)，δ(s,v)?δ(s,u)+w(u,v)。 上限性質：δ(s,v)?d[v]，即d[v]總是s?v的最短距離上限。一旦d[v]=δ(s,v)，則Relaxation不會更改d[v]值。 最短路徑與Relaxation的性質 無路徑性質：如果s到v並無路徑，則d[v]=δ(s,v)=∞。 收斂性質：若s?v的最短路徑包含邊(u,v)且d[u]=δ(s,u)，則此時執行Relax(u,v,w)會使得d[v]=δ(s,v)。 最短路徑與Relaxation的性質 Path-relaxation性質：如p=(v0,v1,…,vk)是一個自s=v0?vk的最短路徑， 則依序執行Relax(v0,v1,w)， Relax(v1,v2,w)…， Relax(vk-1,vk,w)會使得d[vk]=δ(s,vk)。 Predecessor graph性質：當經過一連串的Relaxation後，對所有的點v， d[v]=δ(s,v)時，此時對應的Predecessor graph Gπ即是一個Shortest-path tree rooted at s。 Bellman-Ford演算法 可以計算出沒有負迴圈的圖之最短路徑。 Bellman-Ford(G,w,s) { Initialize-Single-Source(G,s) for i = 1 to |V-1| do for each edge (u,v)∈E do Relex(u,v,w) for each edge (u,v)∈E do if d[v]d[u]+w(u,v) then return false //代表有負迴圈 return true //代表計算成功 } Bellman-Ford演算法運作範例 Bellman-Ford演算法運作範例 Bellman-Ford演算法分析 正確性：對所有的邊作一次Relaxation則可將在Shortest-path tree rooted at s中一步可及的path正確計算出。由path-relaxation性質，做完|V|-1次之後，所有的Shortest simple path終點v，d[v]=δ(s,