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