Posted on 2010-10-23 22:01
MiYu 閱讀(1225)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 圖 ) 、
ACM_資料
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋 
(重定向自松弛技術) 單源最短路徑算法中使用了松弛（relaxation）操作。對于每個頂點v∈V，都設置一個屬性d[v]，用來描述從源點s到v的最短路徑上權值的上界，稱為最短路徑估計（shortest-path estimate）。π[v]代表S到v的當前最短路徑中v點之前的一個點的編號,我們用下面的Θ(V)時間的過程來對最短路徑估計和前趨進行初始化。 INITIALIZE-SINGLE-SOURCE(G,s) 1 for each vertex v∈V[G] 2 do d[v]←∞ 3 π[v]←NIL 4 d[s]←0 經過初始化以后，對所有v∈V，π[v]=NIL，對v∈V-{s}，有d[s]=0以及d[v]=∞。 在松弛一條邊(u,v)的過程中，要測試是否可以通過u，對迄今找到的v的最短路徑進行改進；如果可以改進的話，則更新d[v]和π[v]。一次松弛操作可以減小最短路徑估計的值d[v]，并更新v的前趨域π[v](S到v的當前最短路徑中v點之前的一個點的編號)。下面的偽代碼對邊(u,v)進行了一步松弛操作。 RELAX(u, v, w) 1 if(d[v]>d[u]+w(u,v)) 2 then d[v]←d[u]+w(u,v) 3 π[v]←u 每個單源最短路徑算法中都會調用INITIALIZE-SINGLE-SOURCE，然后重復對邊進行松弛的過程。另外，松弛是改變最短路徑和前趨的唯一方式。各個單源最短路徑算法間區別在于對每條邊進行松弛操作的次數，以及對邊執行松弛操作的次序有所不同。在Dijkstra算法以及關于有向無回路圖的最短路徑算法中，對每條邊執行一次松弛操作。在Bellman-Ford算法中，每條邊要執行多次松弛操作。 procedure relax(u,v,w:integer);//多數情況下不需要單獨寫成procedure。 begin if dis+w<dis[v] then begin dis[v]:=dis+w; pre[v]:=u; end end;