最短路算法图论专题培训课件

最短路算法图论2009年春季图算法及其在通信网络中的应用2/55最短路算法12Label-Setting算法Label-Correcting算法毫无疑问，重点将是以Dijkstra算法为代表的Label-Setting算法。3All-Pair最短路算法2009年春季图算法及其在通信网络中的应用3/55Label-Setting算法4基本Dijkstra算法1235分析(Analysis)扩展(Extension)加速(Speedup)应用(Application)2009年春季图算法及其在通信网络中的应用4/55基本Dijkstra算法Dijkstra算法是本课程的核心内容，务必要掌握其思想和具体的编程方法。问题分析代码设计算法示例求解思路伪码描述Dijkstra算法2009年春季图算法及其在通信网络中的应用5/55问题描述单源最短路问题给定有向加权图G(V,E)，给定源点/起始点s，求从s出发到V中其它所有顶点的权重最小的路径。所有这些最短路构成的是一个怎样的子图？树最短路径树假设权重为正整数;连通图;存在多条最短路时,只求1条.为什么一定是树？最短路上的子路径也是最短路最短路径树是生成树么？是的最短路径树是最小生成树么？不一定ASBC11221ASBC122ASBC1212009年春季图算法及其在通信网络中的应用6/55Dijkstra的求解思路算法思路逐步地发展最短路径树，直至它覆盖所有顶点。怎样实现？构造一个循环，每次循环都增加一个顶点到最短路径树上。加哪个顶点？从所有与树邻接的顶点中，选择离源点最近的。怎么知道谁最近？对每个顶点，都用一个距离标记(Label)来记录。哪里来的距离标记？每次循环都需要对距离标记进行更新。如何维护最短路径树？如何选择顶点？如何更新距离标记？树上顶点的集合S。顶点的前继p(i)。FindMin()Update(i)2009年春季图算法及其在通信网络中的应用7/55伪码描述DijkstraAlg(G(V,E),s)FORallvertexjinVDOd(j)=;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILESVDOi=FindMin();S=SU{i};Update(i);ENDWHILEUpdate(i)FOReachedgeeincidenttoiDOIFe.weight+d(i)<d(e.head)THENd(e.head)=e.weight+d(i);p(e.head)=i;ENDIFENDFORFindMin()FindvertexvinV–Swhichhasminimumd(v);RETURNv;d(j):顶点j的距离标记。p(j):顶点j在最短路径树上的前继点。S:最短路径树上的顶点集合。2009年春季图算法及其在通信网络中的应用8/55怎样根据得到的这些信息重构出最短路径？Dijkstra算法示例saedbc2414233220cs2,s4,sDijkstraAlg(G(V,E),s)FORallvertexjinVDOd(j)=;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILESVDOi=FindMin();S=SU{i};Update(i);ENDWHILEUpdate(i)FOReachedgeeincidenttoiDOIFe.weight+d(i)<d(e.head)THENd(e.head)=e.weight+d(i);p(e.head)=i;ENDIFENDFORFindMin()FindvertexvinV–Swhichhasminimumd(v);RETURNv;StepSd(a),p(a)d(b),p(b)d(c),p(c)d(d),p(d)d(e),p(e)012345ssasaesaedsaedbsaedbc2,s2,s6,a6,a6,a6,a6,d6,d6,d4,a4,a4,a4,s3,a3,aa6,a4,a3,aed6,db每条边被检查了(被描黑)几次？如果放松“连通图”假设，如何改进代码？2009年春季图算法及其在通信网络中的应用9/55Dijkstra算法代码设计

DijkstraAlg

d(j)和p(j)如何管理

FindMin

Update从伪码到代码如何实现d(j)和p(j)Option1：单独用数组/vector来实现；Option2：创建一个CVertex类来记录；思路两个方法都可以；使用类便于扩展，也便于封装。细节

构造函数？接口函数？代码设计在CGraph中增加一个CVertex的map创建一个CVertex类在CGraph中增加一个DijkstraAlg函数用一个list来实现暂时标记的顶点集合为每个顶点准备一个CEdge的list如何管理这些CVertex对象？Q1：用什么数据结构？Q2：这个数据结构放在哪里？思路用一个map，以ID为key；放在CGraph里面。细节

如何初始化？什么时候需要查询/访问？

DijkstraAlg函数放在哪里？option1：作为一个独立的函数option2：作为CGraph的成员函数思路两种都可以，但前者需要传入图对象；为了方便，我们放在CGraph里。细节

使用了哪些CGraph里的成员变量？如何设计输出？如何实现FindMin？物理意义：从暂时标记顶点集合（V–S）中找出距离标记最小的顶点。思路用一个list来实现暂时标记顶点集合；用sort来实现对list的排序。细节

如何更改循环判决条件？

list的sort需要能对对象实现比较判决。如何实现Update？物理意义：给定一个顶点，逐一检查/遍历与它关联的边。思路为每个顶点准备一个记录关联边的list；遍历并检查对应的顶点是否需要更新。细节在CGraph里存储这个数据结构？顶点边顶点的操作细节。2009年春季图算法及其在通信网络中的应用10/55DijkstraAlg源码(一)classCGraph{private: intnumVertex,numEdge; list<CEdge*>IncidentList;//所有的边 map<int,CVertex*>mapVID_Vertex;//所有的顶点 list<CVertex*>listTempMark;//暂时标记的顶点集合 map<int,list<CEdge*>>mapVID_listEdge;//记录与顶点关联的出度边 Update(intVID);public: CGraph(char*inputFile); CGraph(list<CEdge*>listEdge); CGraph(CGraph&); ~CGraph(); intgetNumVertex(); intgetNumEdge(); DijkstraAlg(intVID);};classCVertex{public: intd; intp; intID; CVertex(){d=INFINITY;p=NULL;} ~CVertex();};boolpVertexComp(CVertex*x,CVertex*y){if(x->d<y->d)returnTRUE; returnFALSE;};如果sort的是对象本身，可以用重载<来实现。这里sort的是对象指针，所以写了个外部函数。2009年春季图算法及其在通信网络中的应用11/55DijkstraAlg源码(二)voidCGraph::Dijkstra(ints){map<int,CVertex*>::iteratori,iend;iend=mapVID_Vertex.end();for(i=mapVID_Vertex.begin();i!=iend;i++)

{ if(i->second->ID==s) i->second->d=0; listTempMark.pushback(i->second);}Update(s);while(!listTempMark.empty()){ listTempMark.sort(pVertexComp); intj=(*listTempMark.begin())->ID; listTempMark.popfront(); Update(j);}}voidCGraph::Update(intv){list<CEdge*>lEdge=mapVID_listEdge[v];list<CEdge*>::iteratori,iend;iend=lEdge.end();for(i=lEdge.begin();i!=iend;i++){ intw=(*i)->getWeight(); CVertex*h=mapVID_Vertex[(*i)->getHead()]; CVertex*t=mapVID_Vertex[v]; if(t->d+w<h->d) {h->d=t->d+w; h->p=v; }}}2009年春季图算法及其在通信网络中的应用12/55Label-Setting算法4基本Dijkstra算法1235分析(Analysis)扩展(Extension)加速(Speedup)应用(Application)2009年春季图算法及其在通信网络中的应用13/55分析(Analysis)正确性分析和复杂度分析是算法分析中两个主要的内容。复杂度分析正确性分析Dijkstra算法分析2009年春季图算法及其在通信网络中的应用14/55正确性分析kk+1问题变化问题1：Dijkstra算法求出的是从s到其他顶点的最短路么？k=1第一次循环(k=1)时，Dijkstra算法求出的路径是什么？它是从s出发的最短路么？假定第k次循环求得了第k条最短路，问第k+1次循环求得的是第k+1短的路径么？问题2：Dijkstra算法求出的是从s出发的前n条最短路(宿点必须不同)么？YES，OFCOURSEYES，ITIS.sS集合2009年春季图算法及其在通信网络中的应用15/55复杂度分析DijkstraAlg(G(V,E),s)FORallvertexjinVDOd(j)=;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILESVDOi=FindMin();S=SU{i};Update(i);ENDWHILE有几个循环？2FOR循环的操作次数？2nWHILE循环了几次？nWHILE循环的操作次数呢？FindMin从n个数中求最小，复杂度为n；n+(n-1)+…+1n(n-1)/2Update每次循环检查的边的数目都不同；但是都不重复；总共检查了m次总的操作次数为：2n+n(n-1)/2+n+m结论：Dijkstra算法的复杂度为O(n2)2009年春季图算法及其在通信网络中的应用16/55Label-Setting算法4基本Dijkstra算法1235分析(Analysis)扩展(Extension)加速(Speedup)应用(Application)2009年春季图算法及其在通信网络中的应用17/55扩展(Extension)针对不同问题的物理意义，通过扩展Dijkstra算法来达到求解目的。单源单宿最短路问题最短分离路径对问题带宽约束最短路问题最大通过率路径问题Dijkstra算法扩展2009年春季图算法及其在通信网络中的应用18/55单源单宿最短路单源单宿最短路问题给定加权图G，并给定顶点s和d，求从s到d的最小权重路径。如何修改Dijkstra算法来求解这个问题？增加一个判断分支，永久标记d时，停止循环。怎样实现？重载一个2参数的DijkstraAlg函数。这个算法的复杂度是多少？仍然是O(n2)。ProjectNo.2-1给出求解单源单宿问题的代码。要求设计一个CPath类，从Dijkstra计算得到的CVertex中重构出一个CPath对象，并输出。2009年春季图算法及其在通信网络中的应用19/55最大通过率路径最大通过率路径问题给定加权图G，边上权重表示业务流经该边时的通过比例（大于0小于1）。给定源点s，求从s出发到其他顶点的最大通过率路径。ProjectNo.2-2给定加权图G，边上权重代表通过率。给定顶点s，求从s出发到其他顶点的最大通过率路径。路径通过率与边的通过率是什么关系？乘性关系。怎样实现？修改update函数。修改权重，然后调用DijkstraAlg。2009年春季图算法及其在通信网络中的应用20/55带宽约束下的最短路带宽约束下的最短路问题给定加权图G，每条边上既有权重，也有capacity。给定源点s，以及带宽需求C。求从s出发到其他顶点的带宽大于C的最小权重路径。求解思路？先删除capacity小于C的边，然后在这个新的图上调用DijkstraAlg。怎样实现？需要遍历所有的边，即IncidentList。根据IncidentList求mapVID_listEdge，然后调用DijkstraAlg。ProjectNo.2-3给出求解带宽约束最短路问题的代码。要求设计一个CGraph的成员函数来实现边的删除。2009年春季图算法及其在通信网络中的应用21/55最短分离路径对

(ShortestDisjointPathPair)最短分离路径对问题给定加权图G。给定源点s和宿点d。求从s出发到d的一对路径（两条），要求这两条路径“链路分离”，且路径权重之和最小。NaïveIdea在G上求最短路p；删除p上边，得到新图G’；在G’上求最短路p’；输出p和p’。Suurballe算法在G上求最短路p；p上边反向，得到新图G’；在G’上求最短路p’；删除p和p’中重复的边；重新组合p和p’中的边。bscd44111算法不完备。bacd44111e88不是最佳解。bacd44111bacd441112009年春季图算法及其在通信网络中的应用22/55Label-Setting算法4基本Dijkstra算法1235分析(Analysis)扩展(Extension)加速(Speedup)应用(Application)2009年春季图算法及其在通信网络中的应用23/55加速(Speedup)本课程略去了利用各种“堆”数据结构来实现Dijkstra算法加速的内容。着重讲一种理论上有效（且有趣）的加速方法，以及两种现实中很有效的方法。Dial实现A*算法双向Dijkstra算法Dijkstra算法加速2009年春季图算法及其在通信网络中的应用24/55Dial实现通过降低FindMin的复杂度来加速目的Bucket(k)={iiV,d(i)=k}方法令C表示最大的权重，则距离标记最大为nC。换句话说，最多nC个桶，FindMin复杂度为O(nC)。性能每次Update时，也需要更新桶。更新2009年春季图算法及其在通信网络中的应用25/55Dijkstra算法的Dial实现saedbc2414233220cs2,s4,sDijkstraAlg(G(V,E),s)FORallvertexjinVDOd(j)=;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILESVDOi=FindMin();S=SU{i};Update(i);ENDWHILEStepSd(a),p(a)d(b),p(b)d(c),p(c)d(d),p(d)d(e),p(e)012345ssasaesaedsaedbsaedbc2,s2,s6,a6,a6,a6,a6,d6,d6,d4,a4,a4,a4,s3,a3,aa6,a4,a3,aed6,db01234567=nC=24abcdeaebdec2009年春季图算法及其在通信网络中的应用26/55实现细节提示Dial算法实现难点难点1：基于桶的FindMin难点2：桶的更新//桶的实现：map<int,map<int,CVertex*>>mapBuckets;内层的map的key是顶点ID。该map代表单个的桶。外层的map的key是距离标记。该map代表所有的桶。//指向桶的迭代器map<int,map<int,CVertex*>>::iterator

itBucket;FindMin中，用于指向具体的桶。递增该迭代器，直至对应的桶的empty函数返回FALSE。Hint1Hint2Hint3Update时，如果某个顶点的距离标记从x变到了y，先根据x查找mapBuckets再根据其ID定位到它在内层map中的位置，然后取出该顶点。根据y找到新的桶的位置，做一个pair，把它插入这个桶。2009年春季图算法及其在通信网络中的应用27/55加速(Speedup)本课程略去了利用各种“堆”数据结构来实现Dijkstra算法加速的内容。着重讲一种理论上有效（且有趣）的加速方法，以及两者现实中很有效的方法。Dial实现A*算法双向Dijkstra算法Dijkstra算法加速2009年春季图算法及其在通信网络中的应用28/55反向Dijkstra算法反向最短路问题给定宿点d，求从其他顶点出发到d的最短路径。注意，CGraph中的mapVID_listEdge只记录了出度边；另外构造一个类似的数据结构，记录每个顶点的入度边:mapVID_listRevEdge；在进行Update时不按mapVID_listEdge来更新，而是按照后一个数据结构来更新。ascb53242d2Dijkstra算法ascb53242d2反向Dijkstra算法这就是所谓反向Dijkstra算法。2009年春季图算法及其在通信网络中的应用29/55双向Dijkstra算法针对单源单宿最短路问题，同时运行正向和反向Dijkstra算法，以期减少不必要的永久标记点。目的交替地从V–SF和V–SB中选择顶点进行永久标记，直至SF和SB存在相同点w时停止。方法P(s,w)+P(w,d)P(s,u)+e(u,v)+P(v,d),foralluSF,vSB上述路径中具有最小权重的路径作为输出。比较只要不是给定的宿点，都不必要。SF表示正向算法中的永久标记顶点集合。e(u,v)表示从顶点u到v的一条有向边。SB表示反向算法中的永久标记顶点集合。P(x,y)表示从x到y的最短路径。为什么要进行这样的比较？说明：ascb53242d2交集为c，但sacd的距离大于sabd2009年春季图算法及其在通信网络中的应用30/55实现细节提示双向Dijkstra实现难点难点1：要改变循环体。难点3：拼凑和比较。难点2：要增加数据结构。Hint1循环的终止条件为某个顶点被两个方向都永久标记。循环体中要同时进行两个方向的FindMin和Update。Hint2CVertex中要记录两个方向的距离和前继。CGraph中要增加mapVID_listRevEdge。Hint3逐一检查SF中的顶点，看他的邻接点是否在SB中。如果存在，就重构出一条完整的路径p(从s到d)，放入一个list<CPath*>中。对这个list<CPath*>排序，然后输出第一个元素。2009年春季图算法及其在通信网络中的应用31/55研究性Project自己设计实验，并通过大量实验结果来得出你的结论。提交研究报告。包括问题的描述；求解方法的描述；实验设计思路；结果分析；结论；改进实验的方向等。研究性Project的要求研究性ProjectNo.R1下面两项任选一项：A）对比/定量研究Dijkstra算法和Dial算法的性能。B）对比/定量研究Dijkstra算法和双向Dijkstra算法的性能。2009年春季图算法及其在通信网络中的应用32/55加速(Speedup)本课程略去了利用各种“堆”数据结构来实现Dijkstra算法加速的内容。着重讲一种理论上有效（且有趣）的加速方法，以及两者现实中很有效的方法。Dial实现A*算法双向Dijkstra算法Dijkstra算法加速2009年春季图算法及其在通信网络中的应用33/55A*算法同样是针对单源单宿最短路问题，采用特定的顶点距离标记方法来减少不必要的永久标记点。目的不是把d(j)的大小作为FindMin的依据，而是把d(j)+h(j)作为依据。方法以欧氏距离作h(j)，并更改所有边的权重：e(u,v).weight=e(u,v).weight+h(v)–h(u)在新图上调用Dijkstra算法。实现h(j)表示顶点j到宿点d的距离下限h(j)是启发式方法得到的，通信网中可用欧氏距离e(u,v)表示从顶点u到v的一条有向边。为什么A*等效于更改权重后的Dijkstra？说明：asbh(b)w1dw2h(s)h(a)w1’=w1+h(a)–h(s)w2’=w2+h(b)–h(a)d’(b)=w1’+w2’=w1+w2+h(b)–h(s)=d(b)+h(b)–h(s)与A*要求的距离标记只差一个常量(–h(s))。2009年春季图算法及其在通信网络中的应用34/55Label-Setting算法4基本Dijkstra算法1235分析(Analysis)扩展(Extension)加速(Speedup)应用(Application)2009年春季图算法及其在通信网络中的应用35/55应用：链路状态路由协议OSPF(OpenShortestPathFirst)协议是IP网络中链路状态协议的代表。其中采用的就是Dijkstra算法。路由器如何实现转发？什么情况下不一致？分布式判决能否一致？转发表是怎么来的？怎样应用Dijkstra算法？OSPF协议2009年春季图算法及其在通信网络中的应用36/55转发表目的端口表项1A2表项2B2表项3C3表项n……目的地址B目的地址A目的地址C端口2端口1端口3R路由器R的转发表IP路由原理CAHi！对每个包进行独立的转发判决每个包都自己描述自己源地址目的地址内容怎么可能如何描述如何转发目的地址+转发表什么是转发表转发表是怎么得到的？R凭什么决定去往目的地A应该走端口2，而不是端口1？因为端口2对应的链路在从R到A的最短路上怎么算的最短路？Dijkstra算法图的数据哪里来？静态配置无法适应动态变化，所以采用一个协议，由每个路由器动态、分布式地自动获取/更新。2009年春季图算法及其在通信网络中的应用37/55链路状态协议发布者1序号时间2234422发布者2序号时间123146发布者3序号时间14214154发布者4序号时间122263151065发布者5序号时间3441063发布者6序号时间4553213456435611421022213456435611421022ABIJCDEFG链路状态信息的产生链路状态信息的洪泛拓扑图的构造XABCDACBD链路状态更新是定时的，或检测到变化。最终所有路由器都获得了全局拓扑信息。2009年春季图算法及其在通信网络中的应用38/55分布式判决的一致性ABCDEF5212331321路由器只能控制路径的下一跳，后面的路由器独立做出转发判决。这种分布式判决机制是否存在不一致性？311939不会的。因为最短路的子路径必然也是最短路。如果存在多条最短路，不就会产生不一致么？这不是不一致，因为两条路径权重一样。如果两个路由器对拓扑的理解不同呢？是的，这样会导致不一致。D知道该变化，但A不知道。如果A知道，会有什么不一样？但是，链路状态协议就是为了保证不会出现这种情况。难道链路状态协议在任何情况下都能保证这种一致性？A以为到F的最短路E以为到F的最短路会出现这种情况么？不一定。因为链路状态的更新是需要时间的。更新完成以前就可能出现不一致。最典型的例子就是链路失效。链路发生失效后，E知道，而D不知道。E以为到C的最短路是什么？D以为到C的最短路是什么？在D获知状态更新之前，目的为C的分组路由成环，延迟，丢失。失效的快速恢复是前沿课题。2009年春季图算法及其在通信网络中的应用39/55最短路算法12Label-Setting算法Label-Correcting算法Dijkstra算法只适用于正权重图，针对具有负权重（甚至负圈）的图，该怎么办？3All-Pair最短路算法2009年春季图算法及其在通信网络中的应用40/55Label-Correcting算法负权重1235一般的Label-CorrectingBellman-Ford算法应用2009年春季图算法及其在通信网络中的应用41/55负权重Dijkstra算法为什么只能用于非负权重的图？之所以FindMin得到的顶点可以被永久标记，因为该顶点的距离不可能被改进了。如果存在负权重，这个逻辑不再成立。ascb6224ascb5126d1负权重有什么用？虽然通信网络中很少会出现负权重，但在其他问题中有可能。《AlgorithmsinJava》3rded。21.7节有这样一个例子。更糟的情况：不仅有负权重，而且存在负圈。如果不要求解必须为简单路径，那么不存在最短路。如果要求解必须为简单路径，那么该问题是NP完全问题，与最长路问题一样难。怎么办？能否找到一个算法，可在任意权重的图中求最短路。如果存在最短路，就求出来，如果存在负圈，就检测出来。Label-Correcting算法就能达到这个目的。Bellman-Ford算法是Label-Correcting算法的一个特例。工程中，一般用Dijkstra算法（因为它快）；当出现负权重时，用Bellman-Ford算法。2009年春季图算法及其在通信网络中的应用42/55Label-Correcting算法负权重1235一般的Label-CorrectingBellman-Ford算法应用2009年春季图算法及其在通信网络中的应用43/55基本思想基本思路找到最短路的某些特征。

设计一个算法不断地改进解的性能，直到解呈现出这些特征。最优性条件令d(j)表示源点s到顶点j的距离标记。所有顶点的距离标记就是最短路距离值的充要条件是：对所有的边e(i,j)，都有d(j)d(i)+we(i,j)必要性：

如果所有距离标记等于最短路的距离，那么它们必然满足上述条件。证明：

如果d(j)大于d(i)+we，那么至少存在一条路径sij的距离小于d(j)。矛盾。充分性：

如果所有距离标记都满足上述条件，那么它们就是最短路的距离。证明：

任取一条P(sj)；该路径上的每条边都可以写出上述不等式；求和可知：d(j)是所有P(sj)的距离下限。算法设计检查图中边e(i,j)，若它不满足最优性条件，就更新其距离标记：d(j)=d(i)+we(i,j)2009年春季图算法及其在通信网络中的应用44/55一般的Label-Correcting算法Label_Correcting(G(V,E),s)FORallvertexjinVDOd(j)=;p(j)=NULL;ENDFORd(s)=0;p(s)=NULL;WHILEsomee(i,j)satisfiesd(j)>d(i)+weDOd(j)=d(i)+we;p(j)=i;ENDWHILE分析负圈实现正确性：

该算法可以在有限步骤内收敛到最佳解。复杂度：

最坏复杂度为O(n2C)。怎么检测负圈？

如果某个距离标记小于等于nC时，必然存在负圈。灵活性：

可以用任意方式/顺序检查边，都能保证收敛。但是：

总得有个具体的方法吧。况且：

就没有复杂度更低的实现方法了么？2009年春季图算法及其在通信网络中的应用45/55Label-Correcting算法负权重1235一般的Label-CorrectingBellman-Ford算法应用2009年春季图算法及其在通信网络中的应用46/55FIFO实现(Bellman-Ford)算法描述算法由n次循环构成。每次循环都遍历所有的m条边，发现某条边不满足最优性条件，就更新。

如果第n次循环还有更新，说明有负圈。为什么n次循环就够了？为什么第n次有更新就说明存在负圈？1）s到任一其他顶点的最短路径最多n1跳（即经过n1条边）。除非存在负圈。2）假如s到j实际上的最短路有k跳，那么k轮循环后，d(j)必然会被更新为d*(j)。d*(x)表示s到x的最短路的距离。上述事实意味着，该算法最多经过n1轮循环就可以保证所有的距离标记都更新为最佳值。除非存在负圈。k=1第一次循环(k=1)后，具有最短路跳数为1的那些顶点的距离标记会被更新为最佳值么？YES，OFCOURSEkk+1假定第k次循环后，所有具有最短路跳数小于等于k的那些顶点标记都被更新为最佳值了。问k+1次循环后，还是这样么？YES，ITIS.usvk跳k+1跳k轮后，必有d(u)=d*(u)k+1轮检查e(u,v)时d(v)d*(u)+we?d(v)<d*(u)+we?k+1轮结束后，必有d(v)=d*(u)+we=d*(v)这不可能，因为与假设矛盾显然，Bellman-Ford算法的复杂度为O(nm)。2009年春季图算法及其在通信网络中的应用47/55加速3sabfedc23316-232-44300+3

?33+2

?536946第一轮结束后，顶点s和c没有被更新。第二轮呢？除了c和e外，都没有更新。2第三轮呢？所有顶点都没有更新。第四、五和六轮呢？浪费。Modified_Label_Correcting(G(V,E),s)FORallvertexjinVDOd(j)=;p(j)=NULL;d(s)=0;p(s)=NULL;LIST={s};WHILELIST非空DO

从LIST中取出一个顶点i；

FORi的所有关联边DOIFd(j)>d(i)+weDOd(j)=d(i)+we;p(j)=i;

若jLIST就插入LIST；ENDWHILE一次循环中，不必检查所有的边。上一轮中没有更新的顶点所“发出”的边都不必检查。不需要n轮循环。只要能检测出某一轮中没有更新距离标记，就可以终止循环。除非存在负圈。0LIST={s}3LIST={}LIST={a}6LIST={af}3LIST={afe}LIST={fe}5LIST={feb}4LIST={eb}6LIST={ebd}LIST={bd}LIST={d}LIST={}2LIST={e}9LIST={ec}LIST={c}LIST={}2009年春季图算法及其在通信网络中的应用48/55Label-Correcting算法负权重1235一般的Label-CorrectingBellman-Ford算法应用2009年春季图算法及其在通信网络中的应用49/55ABCD21371应用：距离矢量路由协议目的距离端口B2BC7CD-目的距离端口A2AC1CD3D目的距离端口A7AB1BD1D顶点i的距离标记什么时候需要更新？当i的反向邻接点发生了更新时。反过来，i到某个目的点d的距离何时更新？当i的正向邻接点到d的距离发生了更新时。只要i的邻接点不断地告诉i它们到其它目的点的距离发生了怎样的变化，i就可以据此计算它到网络中其它点怎么走最短。分布式计算。目的距离端口A-B3BC1C这种分布式迭代计算是否能保证收敛？Label-Correcting算法的原理保证了其收敛性。CA距离矢量更新消息8CBA3B5BACABCD8C2CBC3BBD5BCBDB2CDC这只是第1轮；每当路由器发生了更新，他就将其新的距离矢量发给他的邻接点(注意：不是洪泛)；直至没有更新为止。2009年春季图算法及其在通信网络中的应用50/55最短路算法12Label-Setting算法Label-Correcting算法Dijkstra算法和Bellman-Ford算法解决的是单源最短路问题。那么，针对All-Pair最短路问题，是否存在更简单的算法？3All-Pair最短路算法2009年春季图算法及其在通信网络中的应用51/55重复最短路基本思路调用单源最短路算法n次。每次针对不同的源点。复杂度？假如使用的最短路算法复杂度为S(n,m,C)，则为O(nS(n,m,C))。选哪个最短路算法好？当然是Dijkstra好啰，因为它快嘛。存在负权重怎么办？调用n遍Bellman-Ford呗，还能怎么办？算法设计1遍Bellman-Ford加上(n–1)遍Dijkstra第一次Bellman-Ford后，如果存在负圈，整个问题无解。如果没有负圈，对所有边进行如下权重变换：w’e(i,j)=we(i,j)+d(i)–d(j)这怎么可能？因为如果存在负圈，无论从哪个源点出发进行Bellman-Ford都能检测出来。还因为利用得到的距离标记，可以将边的权重变换为非负值。在新图上，从其它顶点出发分别调用1次Dijkstra算法。asbd(b)d(a)w2009年春季图算法及其在通信网络中的应用52/55All-PairLabel-Correcting最优性条件令d(i,j)表示从