最短路算法(图论).ppt

1、图算法及其在通信网中的应用,王晟 博士 教授 博导,Part 05: 最短路算法,1,2 / 55,最短路算法,1,2,Label-Setting算法,Label-Correcting算法,毫无疑问，重点将是以Dijkstra算法为代表的Label-Setting算法。,3 / 55,Label-Setting算法,4,基本Dijkstra算法,1,2,3,5,分析(Analysis),扩展(Extension),加速(Speed up),应用(Application),4 / 55,基本Dijkstra算法,Dijkstra算法是本课程的核心内容，务必要掌握其思想和具体的编程方法。,问题分析

2、,代码设计,算法示例,求解思路,伪码描述,Dijkstra算法,5 / 55,问题描述,所有这些最短路构成的是一个怎样的子图？,为什么一定是树？,最短路径树是生成树么？,最短路径树是最小生成树么？,6 / 55,Dijkstra的求解思路,如何维护最短路径树？,如何选择顶点？,如何更新距离标记？,7 / 55,伪码描述,d(j): 顶点j的距离标记。,p(j): 顶点j在最短路径树上的前继点。,S: 最短路径树上的顶点集合。,8 / 55,怎样根据得到的这些信息重构出最短路径？,Dijkstra算法示例,0,c,s,2,s,4,s,s,sa,sae,saed,saedb,saedbc,2, s

3、,2, s,6, a,6, a,6, a,6, a,6, d,6, d,6, d,4, a,4, a,4, a,4, s,3, a,3, a,a,6,a,4,a,3,a,e,d,6,d,b,每条边被检查了(被描黑)几次？,如果放松“连通图”假设，如何改进代码？,9 / 55,Dijkstra算法代码设计,DijkstraAlg,d(j)和p(j),如何管理,FindMin,Update,10 / 55,DijkstraAlg源码(一),class CGraph private: int numVertex, numEdge; list IncidentList; / 所有的边 map mapV

4、ID_Vertex; / 所有的顶点 list listTempMark; / 暂时标记的顶点集合 map mapVID_listEdge; / 记录与顶点关联的出度边 Update(int VID); public: CGraph(char* inputFile); CGraph(list listEdge); CGraph(CGraph ,class CVertex public: int d; int p; int ID; CVertex()d = INFINITY; p = NULL; CVertex(); ; bool pVertexComp ( CVertex* x, CVerte

5、x* y ) if ( x-d d ) return TRUE; return FALSE; ;,如果sort的是对象本身，可以用重载来实现。这里sort的是对象指针，所以写了个外部函数。,11 / 55,DijkstraAlg源码(二),void CGraph:Dijkstra(int s) map:iterator i,iend; iend = mapVID_Vertex.end(); for( i=mapVID_Vertex.begin(); i != iend; i+) if ( i-second-ID = s) i-second-d = 0; listTempMark.pushbac

6、k(i-second); Update(s); while( ! listTempMark.empty() ) listTempMark.sort(pVertexComp); int j = (*listTempMark.begin()-ID; listTempMark.popfront(); Update(j); ,void CGraph:Update(int v) list lEdge = mapVID_listEdgev; list:iterator i,iend; iend = lEdge.end(); for( i = lEdge.begin(); i!=iend; i+) int

7、w = (*i)-getWeight(); CVertex* h = mapVID_Vertex(*i)-getHead(); CVertex* t = mapVID_Vertexv; if ( t-d + w d ) h-d = t-d + w; h-p = v; ,12 / 55,Label-Setting算法,4,基本Dijkstra算法,1,2,3,5,分析(Analysis),扩展(Extension),加速(Speed up),应用(Application),13 / 55,分析(Analysis),正确性分析和复杂度分析是算法分析中两个主要的内容。,复杂度分析,正确性分析,Dij

8、kstra算法分析,14 / 55,正确性分析,问题1：Dijkstra算法求出的是从s到其他顶点的最短路么？,第一次循环(k=1)时，Dijkstra算法求出的路径是什么？它是从s出发的最短路么？,假定第k次循环求得了第k条最短路，问第k+1次循环求得的是第k+1短的路径么？,问题2：Dijkstra算法求出的是从s出发的前n条最短路(宿点必须不同)么？,YES，OF COURSE,YES，IT IS.,15 / 55,复杂度分析,2,2n,n,总的操作次数为： 2n + n(n-1)/2 + n + m,结论： Dijkstra算法的复杂度为O(n2),16 / 55,Label-Sett

9、ing算法,4,基本Dijkstra算法,1,2,3,5,分析(Analysis),扩展(Extension),加速(Speed up),应用(Application),17 / 55,扩展(Extension),针对不同问题的物理意义，通过扩展Dijkstra算法来达到求解目的。,单源单宿最短路问题,最短分离路径对问题,带宽约束最短路问题,最大通过率路径问题,Dijkstra算法扩展,18 / 55,单源单宿最短路,19 / 55,最大通过率路径,20 / 55,带宽约束下的最短路,21 / 55,最短分离路径对(Shortest Disjoint Path Pair),b,s,c,d,4,

10、4,1,1,1,算法不完备。,b,a,c,d,4,4,1,1,1,e,8,8,不是最佳解。,b,a,c,d,4,4,1,1,1,b,a,c,d,4,4,1,1,1,22 / 55,Label-Setting算法,4,基本Dijkstra算法,1,2,3,5,分析(Analysis),扩展(Extension),加速(Speed up),应用(Application),23 / 55,加速(Speed up),本课程略去了利用各种“堆”数据结构来实现Dijkstra算法加速的内容。着重讲一种理论上有效（且有趣）的加速方法，以及两种现实中很有效的方法。,Dial实现,A*算法,双向Dijkstra

11、算法,Dijkstra算法加速,24 / 55,Dial实现,25 / 55,Dijkstra算法的Dial实现,0,c,s,2,s,4,s,s,sa,sae,saed,saedb,saedbc,2, s,2, s,6, a,6, a,6, a,6, a,6, d,6, d,6, d,4, a,4, a,4, a,4, s,3, a,3, a,a,6,a,4,a,3,a,e,d,6,d,b,a,b,c,d,e,a,e,b,d,e,c,26 / 55,实现细节提示,难点1：基于桶的FindMin,难点2：桶的更新,/桶的实现： map mapBuckets;,/指向桶的迭代器 map :iter

12、ator itBucket;,27 / 55,加速(Speed up),本课程略去了利用各种“堆”数据结构来实现Dijkstra算法加速的内容。着重讲一种理论上有效（且有趣）的加速方法，以及两者现实中很有效的方法。,Dial实现,A*算法,双向Dijkstra算法,Dijkstra算法加速,28 / 55,反向Dijkstra算法,注意，CGraph中的mapVID_listEdge只记录了出度边； 另外构造一个类似的数据结构，记录每个顶点的入度边:mapVID_listRevEdge； 在进行Update时不按mapVID_listEdge来更新，而是按照后一个数据结构来更新。,Dijkst

13、ra算法,反向Dijkstra算法, 这就是所谓反向Dijkstra算法。,29 / 55,双向Dijkstra算法,交集为c，但sacd的距离大于sabd,30 / 55,实现细节提示,难点1：要改变循环体。,难点3：拼凑和比较。,难点2：要增加数据结构。,31 / 55,研究性Project,32 / 55,加速(Speed up),本课程略去了利用各种“堆”数据结构来实现Dijkstra算法加速的内容。着重讲一种理论上有效（且有趣）的加速方法，以及两者现实中很有效的方法。,Dial实现,A*算法,双向Dijkstra算法,Dijkstra算法加速,33 / 55,A*算法,34 / 55

14、,Label-Setting算法,4,基本Dijkstra算法,1,2,3,5,分析(Analysis),扩展(Extension),加速(Speed up),应用(Application),35 / 55,应用：链路状态路由协议,OSPF(Open Shortest Path First)协议是IP网络中链路状态协议的代表。其中采用的就是Dijkstra算法。,路由器如何实现转发？,什么情况下不一致？,分布式判决能否一致？,转发表是怎么来的？,怎样应用Dijkstra算法？,OSPF协议,36 / 55,转发表,路由器R的转发表,C,A,Hi！,对每个包进行独立的转发判决,每个包都自己描述自

15、己,怎么可能,如何描述,如何转发,目的地址+转发表,什么是转发表,因为端口2对应的链路在从R到A的最短路上,Dijkstra算法,静态配置无法适应动态变化，所以采用一个协议，由每个路由器动态、分布式地自动获取/更新。,37 / 55,链路状态协议,2,1,3,4,5,6,4,3,5,6,1,1,4,2,10,22,A,C,B,D,链路状态更新是定时的，或检测到变化。,最终所有路由器都获得了全局拓扑信息。,38 / 55,分布式判决的一致性,31,19,39,不会的。因为最短路的子路径必然也是最短路。,这不是不一致，因为两条路径权重一样。,是的，这样会导致不一致。,D知道该变化，但A不知道。,如

16、果A知道，会有什么不一样？,但是，链路状态协议就是为了保证不会出现这种情况。,A以为到F的最短路,E以为到F的最短路,会出现这种情况么？,不一定。因为链路状态的更新是需要时间的。更新完成以前就可能出现不一致。,最典型的例子就是链路失效。,链路发生失效后，E知道，而D不知道。,E以为到C的最短路是什么？,D以为到C的最短路是什么？,在D获知状态更新之前，目的为C的分组路由成环，延迟，丢失。,失效的快速恢复是前沿课题。,39 / 55,最短路算法,1,2,Label-Setting算法,Label-Correcting算法,Dijkstra算法只适用于正权重图，针对具有负权重（甚至负圈）的图，该怎

17、么办？,40 / 55,Label-Correcting算法,负权重,1,2,3,5,一般的Label-Correcting,Bellman-Ford算法,应用,41 / 55,负权重,之所以FindMin得到的顶点可以被永久标记，因为该顶点的距离不可能被改进了。如果存在负权重，这个逻辑不再成立。,虽然通信网络中很少会出现负权重，但在其他问题中有可能。Algorithms in Java3rd ed。21.7节有这样一个例子。,如果不要求解必须为简单路径，那么不存在最短路。,如果要求解必须为简单路径，那么该问题是NP完全问题，与最长路问题一样难。,Label-Correcting算法就能达到这

18、个目的。,Bellman-Ford算法是Label-Correcting算法的一个特例。,工程中，一般用Dijkstra算法（因为它快）；当出现负权重时，用Bellman-Ford算法。,42 / 55,Label-Correcting算法,负权重,1,2,3,5,一般的Label-Correcting,Bellman-Ford算法,应用,43 / 55,基本思想,必要性： 如果所有距离标记等于最短路的距离，那么它们必然满足上述条件。,证明： 如果d(j)大于d(i)+we，那么至少存在一条路径sij的距离小于d(j)。矛盾。,充分性： 如果所有距离标记都满足上述条件，那么它们就是最短路的距离

19、。,证明： 任取一条P(sj)；该路径上的每条边都可以写出上述不等式；求和可知：d(j)是所有P(sj)的距离下限。,44 / 55,一般的Label-Correcting算法,正确性： 该算法可以在有限步骤内收敛到最佳解。,复杂度： 最坏复杂度为O(n2C)。,灵活性： 可以用任意方式/顺序检查边，都能保证收敛。,但是： 总得有个具体的方法吧。,况且： 就没有复杂度更低的实现方法了么？,45 / 55,Label-Correcting算法,负权重,1,2,3,5,一般的Label-Correcting,Bellman-Ford算法,应用,46 / 55,FIFO实现(Bellman-Ford

20、),1）s到任一其他顶点的最短路径最多n1跳（即经过n1条边）。除非存在负圈。,2）假如s到j实际上的最短路有k跳，那么k轮循环后，d(j)必然会被更新为d*(j)。d*(x)表示s到x的最短路的距离。,上述事实意味着，该算法最多经过n1轮循环就可以保证所有的距离标记都更新为最佳值。除非存在负圈。,第一次循环(k=1)后，具有最短路跳数为1的那些顶点的距离标记会被更新为最佳值么？,YES，OF COURSE,假定第k次循环后，所有具有最短路跳数小于等于k的那些顶点标记都被更新为最佳值了。问k+1次循环后，还是这样么？,YES，IT IS.,k轮后，必有d(u)=d*(u),k+1轮检查e(u,

21、v)时,d(v) d*(u)+we?,d(v) d*(u)+we?,k+1轮结束后，必有 d(v) = d*(u)+we = d*(v),这不可能，因为与假设矛盾,47 / 55,加速,0+3 ?,3,3+2 ?,5,3,6,9,4,6,第一轮结束后，顶点s和c没有被更新。,第二轮呢？,除了c和e外，都没有更新。,2,第三轮呢？,所有顶点都没有更新。,第四、五和六轮呢？,浪费。,0,LIST = s,3,LIST = ,LIST = a,6,LIST = af,3,LIST = afe,LIST = fe,5,LIST = feb,4,LIST = eb,6,LIST = ebd,LIST = bd,LIST = d,LIST = ,2,LIST = e,9,LIST = ec,LIST = c,LIST = ,48 / 55,Label-Correcting算法,负权重,1,2,3,5,一般的Label-Correcting,Bellman-Ford算法,应用,49 / 55,应用：距离矢量路由协议,当i的反向邻接点发生了更新时。,当i 的正向邻接点到d 的距离发生了更新时。,CA,距离矢量更新消息,BA,AC,AB,CD,BC,BD,CB,DB,DC,这只是第1轮； 每当路由器发生了更新，他