精品文档多阶段决策过程multistepdecisionprocess是指这样一类特殊的

1、第七部分 最短路径（Shortest-paths）71 问题描述在一个带权的无向或者有向图中，如果从图中某顶点（称源点）到达另顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。实际应用中，有把交通运输网络作为一个图，图中顶点表示城市，图中各边表示城市之间的交通运输线。边上的权值就根据具体需要，可以用各种代价表示，比如路程，运费，时间。同时，可以用有向图表示往返代价的不一致。计算机网络中，把网络结构看成带权图，路由选择的时候采用的固定路由算法其中有使用最短路径算法。此外，最短路径算法还应用于电子导航中，根据已知地理网络，得出合适的航线；应用于电力、通讯等

2、各种管网、管线的布局设计，城市规划等等。由于应用的需要，最短路径算法问题成为计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。在最短路径问题中，给出的是一个带权有向图G(V, E)，加权函数w:EàR为从边到实型权值的映射。路径p=(v0,v1,v2,vk)的权是指组成边的所有权值之和：w(p)=w(vi-1,vi) i=1k;定义从u到v间的最短路径的权为：从顶点u到v的最短路径定义为权w(p)=&(u,v)的任何路径.不带权图的最短路径问题是一个特例，可将图视为没条边的权值均为1的带权图。两种最常见的最短路径问题：l 从某个源点到其余各顶点的最短路

3、径l 每对顶点间的最短路径72松弛技术Relaxation在后面介绍的几个算法中都用到了松弛技术，现在就来看看松弛技术。对于每个顶点vV，都设置一个属性dv，用来描述从源点s到v的最短路径上权值的上界，称为最短路径估计（shortest-path estimate）。我们用下面的(V)时间的过程来对最短路径估计和前趋进行初始化。INITIALIZE-SINGLE-SOURCE(G,s)1 for each vertex vVG2 do dv3 vNIL4 ds0经过初始化以后，对所有vV，v=NIL，对vV-s，有ds=0以及dv=。在松弛一条边(u,v)的过程中，要测试是否可以通过u，对迄今

4、找到的v的最短路径进行改进；如果可以改进的话，则更新dv和v。一次松弛操作可以减小最短路径估计的值dv，并更新v的前趋域v。下面的伪代码对边(u,v)进行了一步松弛操作。RELAX(u, v, w)1 if(dv>du+w(u,v)2 then dvdu+w(u,v)3 vu在Bellman-Ford algorithm和Dijkstras algorithm都会调用到INITIALIZE-SINGLE-SOURCE(G,s)，然后重复对边进行松弛的过程。另外松弛是改变最短路径和前趋的唯一方式，在两个算法之间的区别在于对每条边进行的松弛操作的次数，以及对边执行松弛操作的次序不同。在Dij

5、kstras algorithm以及关于有向无回路图的最短路径算法中，对每条边执行情况一次松弛操作。而在Bellman-Ford算法中，对每条边要执行多次松弛操作。73Bellman-Ford algorithm思想：运用松弛技术，对每一个结点vV，逐步减少从源s到v的最短路径的权的估计值dv，直至其达到实际最短路径的权(s,v)。算法返回布尔值TURE当且仅当图中没有源结点可达的负权回路。优点：解决更一般情况的单源最短路径问题。且边的权值可以为负，可检测出图中是否存在一个从源结点可达的负权回路，如果存在负权回路则无解；否则将产生最短路径及其权。BELLMAN-FORD（G,w,s）1 INI

6、TIALIZE-SINGLE-SOURCE(G,s)2 for iß1 to |VG|-13 do for each edge(u,v)EG4 do RELAX(u,v,w)5 for each edge(u,v) EG6 do if dv>du+w(u,v)7 then return false;8 return true引理 设为带权有向图，其源点为s，权函数为w：EàR，并且假定G中不包含从s点可达的负权回路。那么BELLMAN-FORD第24行循环的|V|-1次迭代后，对任何s可达的顶点v，有dv=(s,v)。推论：设G=（V，E）为带权有向图，源顶点为s，加

7、权函数为w:EàR，对每个顶点v(vV)，从s到v存在一条通路，当且仅当对G运行BELLMAN-FORD（G,w,s）算法，算法终止时，有dv<。定理：设G=（V，E）为带权有向图，源顶点为s，加权函数为w:EàR，对该图运行BELLMAN-FORD（G,w,s）算法，若G不包含s可达的负权回路，则算法返回TRUE，对所有顶点v(vV)，有dv=(s,v)成立。前趋子图G是以s为根的最短路径树。如果G包含从s可达的负权回路，则算法返回FALSE。74 Dijkstras algorithm目的：解决有向加权图的最短路径问题。条件：该图的所有边的权值非负。算法思想：设置

8、一个结点集合S，从源点s到集合中结点的最终最短路径的权均已确定。算法反复挑选出其最短路径估计为最小的结点uV-S，把u插入到集合S中，并对离开u的所有边进行松弛。Dijkstra算法总是在集合V-S中选择“最近”的结点插入集合S中，它使用了贪心策略。Dijkstra(G,w,s)Init-Singlesource(G,s)s = emptyQ = VGwhile ( Q != empty)    do u = extract-min(Q)        s = s and u 

9、0;      for 每个顶点v属于Adju            do Relax(u,v,w)Dijkstra执行过程：定理7.1：Dijkstra算法的正确性证明证明：将证明对每一结点u属于V，当u被插入集合S时有duQ(s,u)成立，且此后该等式一直保持成立。设u为插入集合S中的第一个满足du!=Q(s,u)的结点。可知u!=s，可知u被插入集合S前S!=空。从s到u必存在某条通路，否则du=Q(s,u)inf，与du!=Q(

10、s,u)矛盾。因为存在一条通路，所以存在一条最短路p。路径p联结集合S中的结点S到V-S的结点u。考察沿路径p的第一个属于V-S的结点y。设x属于V是y的先辈。路径p可以分解为sp->x和yp2->u。（若第一个点为u，则du=Q(s,u)，已得证）因为s到u的最短路径上y出现在y之前且所有边的权均为非负，我们有Q(s,y)<=Q(s,u),因而dy = Q(s,y) <= Q(s,u) <=du,但因为在第5行选择u时结点u和y都属于V-S，所以有du<=dy。因此du=dy。最后得出结论du=Q(s,u)，这与我们对u的假设矛盾。Dijkstra算法效率：若用线性数组实现优先队列：每次Extract_Min为O(v)，存在V次，则为O(v2)。for中有E次迭代。所以整个算法运行时间O(V2)。稀疏图用二叉堆比较合适。Extract_Min需要O(lgv)，建立需要O(V)。更改权值用Decrease_key。总时间为O(V+E)lgV)。如果用斐波那契堆可以进一步提高效率至O(VlgV+E)。75 总结 根据各种教材介绍，还有几种经典的算法，所有顶点之间的最短路径（Floyed算法）、特定两个顶点之间的最短路径（A*算法）等。在上述介绍的算法，当减低问题