第1页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共8页第七部分最短路径（Shortest-paths）7．1问题描述在一个带权的无向或者有向图中，如果从图中某顶点（称源点）到达另顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。实际应用中，有把交通运输网络作为一个图，图中顶点表示城市，图中各边表示城市之间的交通运输线。边上的权值就根据具体需要，可以用各种代价表示，比如路程，运费，时间。同时，可以用有向图表示往返代价的不一致。计算机网络中，把网络结构看成带权图，路由选择的时候采用的固定路由算法其中有使用最短路径算法。此外，最短路径算法还应用于电子导航中，根据已知地理网络，得出合适的航线；应用于电力、通讯等各种管网、管线的布局设计，城市规划等等。由于应用的需要，最短路径算法问题成为计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。在最短路径问题中，给出的是一个带权有向图G＝(V,E)，加权函数w:ER为从边到实型权值的映射。路径p=(v0,v1,v2,…,vk)的权是指组成边的所有权值之和：w(p)=∑w(vi-1,vi)i=1—k;定义从u到v间的最短路径的权为：δ(u,v)=¿{min{w(p)}:u⃗pv若从uv到存在一条通路¿¿¿¿从顶点u到v的最短路径定义为权w(p)=&(u,v)的任何路径.不带权图的最短路径问题是一个特例，可将图视为没条边的权值均为1的带权图。两种最常见的最短路径问题：从某个源点到其余各顶点的最短路径每对顶点间的最短路径第2页共8页第1页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共8页7．2松弛技术Relaxation在后面介绍的几个算法中都用到了松弛技术，现在就来看看松弛技术。对于每个顶点v∈V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径估计（shortest-pathestimate）。我们用下面的Θ(V)时间的过程来对最短路径估计和前趋进行初始化。INITIALIZE-SINGLE-SOURCE(G,s)1foreachvertexv∈V[G]2dod[v]←∞3π[v]←NIL4d[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]。下面的伪代码对边(u,v)进行了一步松弛操作。RELAX(u,v,w)1if(d[v]>d[u]+w(u,v))2thend[v]←d[u]+w(u,v)3π[v]←u在Bellman-Fordalgorithm和Dijkstra’salgorithm都会调用到INITIALIZE-SINGLE-SOURCE(G,s)，然后重复对边进行松弛的过程。另外松弛是改变最短路径和前趋的唯一方式，在两个算法之间的区别在于对每条边进行的松弛操作的次数，以及对边执行松弛操作的次序不同。在Dijkstra’salgorithm以及关于有向无回路图的最短路径算法中，对每条边执行情况一次松弛操作。而在Bellman-Ford算法中，对每条边要执行多次松弛操作。7．3Bellman-Fordalgorithm思想：运用松弛技术，对每一个结点v∈V，逐步减少从源s到v的最短路第3页共8页第2页共8页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第3页共8页径的权的估计值d[v]，直至其达到实际最短路径的权δ(s,v)。算法返回布尔值TURE当且仅当图中没有源结点可达的负权回路。优点：解决更一般情况的单源最短路径问题。且边的权值可以为负，可检测出图中是否存在一个从源结点可达的负权回路，如果存在负权回路则无解；否则将产生最短路径及其权。BELLMAN-FORD（G,w,s）1INITIALIZE-SINGLE-SOURCE(G,s)2fori1to|V[G]|-13doforeachedge(u,v)∈E[G]4doRELAX(u,v,w)5foreachedge(u,v)∈E[G]6doifd[v]>d[u]+w(u,v)7thenreturnfalse;8returntrue引理7.3.1设为带权有向图，其源点为s，权函数为w：ER，并且假定G中不包含从s点可达的负权回路。那么BELLMAN-FORD第2—4行循环的|V|-1次迭代后，对任何s可达的顶点v，有d[v]=∮(s,v)。推论：设G=（V，E）为带权有向图，源顶点为s，加权函数为w:ER，对每个顶点v(v∈V)，从s到v存...
