Posted on 2010-10-23 22:01
MiYu 阅读(1180)
评论(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;