最短路算法(图论).ppt

图算法及其在通信网中的应用,王晟 博士 教授 博导,Part 05:最短路算法,2009年春季图算法及其在通信网络中的应用,2/55,最短路算法,1,2,Label-Setting算法,Label-Correcting算法,毫无疑问，重点将是以Dijkstra算法为代表的Label-Setting算法。,2009年春季图算法及其在通信网络中的应用,3/55,Label-Setting算法,4,基本Dijkstra算法,1,2,3,5,分析(Analysis),扩展(Extension),加速(Speed up),应用(Application),2009年春季图算法及其在通信网络中的应用,4/55,基本Dijkstra算法,Dijkstra算法是本课程的核心内容，务必要掌握其思想和具体的编程方法。,问题分析,代码设计,算法示例,求解思路,伪码描述,Dijkstra算法,2009年春季图算法及其在通信网络中的应用,5/55,问题描述,所有这些最短路构成的是一个怎样的子图？,为什么一定是树？,最短路径树是生成树么？,最短路径树是最小生成树么？,2009年春季图算法及其在通信网络中的应用,6/55,Dijkstra的求解思路,如何维护最短路径树？,如何选择顶点？,如何更新距离标记？,2009年春季图算法及其在通信网络中的应用,7/55,伪码描述,d(j):顶点j的距离标记。,p(j):顶点j在最短路径树上的前继点。,S:最短路径树上的顶点集合。,2009年春季图算法及其在通信网络中的应用,8/55,怎样根据得到的这些信息重构出最短路径？,Dijkstra算法示例,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,每条边被检查了(被描黑)几次？,如果放松“连通图”假设，如何改进代码？,2009年春季图算法及其在通信网络中的应用,9/55,Dijkstra算法代码设计,DijkstraAlg,d(j)和p(j),如何管理,FindMin,Update,2009年春季图算法及其在通信网络中的应用,10/55,DijkstraAlg源码(一),class CGraph private:int numVertex,numEdge;list IncidentList;/所有的边map mapVID_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,CVertex*y)if(x-d d)return TRUE;return FALSE;,如果sort的是对象本身，可以用重载来实现。这里sort的是对象指针，所以写了个外部函数。,2009年春季图算法及其在通信网络中的应用,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.pushback(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 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;,2009年春季图算法及其在通信网络中的应用,12/55,Label-Setting算法,4,基本Dijkstra算法,1,2,3,5,分析(Analysis),扩展(Extension),加速(Speed up),应用(Application),2009年春季图算法及其在通信网络中的应用,13/55,分析(Analysis),正确性分析和复杂度分析是算法分析中两个主要的内容。,复杂度分析,正确性分析,Dijkstra算法分析,2009年春季图算法及其在通信网络中的应用,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.,2009年春季图算法及其在通信网络中的应用,15/55,复杂度分析,2,2n,n,总的操作次数为：2n+n(n-1)/2+n+m,结论：Dijkstra算法的复杂度为O(n2),2009年春季图算法及其在通信网络中的应用,16/55,Label-Setting算法,4,基本Dijkstra算法,1,2,3,5,分析(Analysis),扩展(Extension),加速(Speed up),应用(Application),2009年春季图算法及其在通信网络中的应用,17/55,扩展(Extension),针对不同问题的物理意义，通过扩展Dijkstra算法来达到求解目的。,单源单宿最短路问题,最短分离路径对问题,带宽约束最短路问题,最大通过率路径问题,Dijkstra算法扩展,2009年春季图算法及其在通信网络中的应用,18/55,单源单宿最短路,2009年春季图算法及其在通信网络中的应用,19/55,最大通过率路径,2009年春季图算法及其在通信网络中的应用,20/55,带宽约束下的最短路,2009年春季图算法及其在通信网络中的应用,21/55,最短分离路径对(Shortest Disjoint Path Pair),b,s,c,d,4,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,2009年春季图算法及其在通信网络中的应用,22/55,Label-Setting算法,4,基本Dijkstra算法,1,2,3,5,分析(Analysis),扩展(Extension),加速(Speed up),应用(Application),2009年春季图算法及其在通信网络中的应用,23/55,加速(Speed up),本课程略去了利用各种“堆”数据结构来实现Dijkstra算法加速的内容。着重讲一种理论上有效（且有趣）的加速方法，以及两种现实中很有效的方法。,Dial实现,A*算法,双向Dijkstra算法,Dijkstra算法加速,2009年春季图算法及其在通信网络中的应用,24/55,Dial实现,2009年春季图算法及其在通信网络中的应用,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,2009年春季图算法及其在通信网络中的应用,26/55,实现细节提示,难点1：基于桶的FindMin,难点2：桶的更新,/桶的实现：map mapBuckets;,/指向桶的迭代器map:iterator itBucket;,2009年春季图算法及其在通信网络中的应用,27/55,加速(Speed up),本课程略去了利用各种“堆”数据结构来实现Dijkstra算法加速的内容。着重讲一种理论上有效（且有趣）的加速方法，以及两者现实中很有效的方法。,Dial实现,A*算法,双向Dijkstra算法,Dijkstra算法加速,2009年春季图算法及其在通信网络中的应用,28/55,反向Dijkstra算法,注意，CGraph中的mapVID_listEdge只记录了出度边；另外构造一个类似的数据结构，记录每个顶点的入度边:mapVID_listRevEdge；在进行Update时不按mapVID_listEdge来更新，而是按照后一个数据结构来更新。,Dijkstra算法,反向Dijkstra算法,这就是所谓反向Dijkstra算法。,2009年春季图算法及其在通信网络中的应用,29/55,双向Dijkstra算法,交集为c，但sacd的距离大于sabd,2009年春季图算法及其在通信网络中的应用,30/55,实现细节提示,难点1：要改变循环体。,难点3：拼凑和比较。,难点2：要增加数据结构。,2009年春季图算法及其在通信网络中的应用,31/55,研究性Project,2009年春季图算法及其在通信网络中的应用,32/55,加速(Speed up),本课程略去了利用各种“堆”数据结构来实现Dijkstra算法加速的内容。着重讲一种理论上有效（且有趣）的加速方法，以及两者现实中很有效的方法。,Dial实现,A*算法,双向Dijkstra算法,Dijkstra算法加速,2009年春季图算法及其在通信网络中的应用,33/55,A*算法,2009年春季图算法及其在通信网络中的应用,34/55,Label-Setting算法,4,基本Dijkstra算法,1,2,3,5,分析(Analysis),扩展(Extension),加速(Speed up),应用(Application),2009年春季图算法及其在通信网络中的应用,35/55,应用：链路状态路由协议,OSPF(Open Shortest Path First)协议是IP网络中链路状态协议的代表。其中采用的就是Dijkstra算法。,路由器如何实现转发？,什么情况下不一致？,分布式判决能否一致？,转发表是怎么来的？,怎样应用Dijkstra算法？,OSPF协议,2009年春季图算法及其在通信网络中的应用,36/55,转发表,路由器R的转发表,C,A,Hi！,对每个包进行独立的转发判决,每个包都自己描述自己,怎么可能,如何描述,如何转发,目的地址+转发表,什么是转发表,因为端口2对应的链路在从R到A的最短路上,Dijkstra算法,静态配置无法适应动态变化，所以采用一个协议，由每个路由器动态、分布式地自动获取/更新。,2009年春季图算法及其在通信网络中的应用,37/55,链路状态协议,2,1,3,4,5,6,4,3,5,6,1,1,4,2,10,22,A,C,B,D,链路状态更新是定时的，或检测到变化。,最终所有路由器都获得了全局拓扑信息。,2009年春季图算法及其在通信网络中的应用,38/55,分布式判决的一致性,31,19,39,不会的。因为最短路的子路径必然也是最短路。,这不是不一致，因为两条路径权重一样。,是的，这样会导致不一致。,D知道该变化，但A不知道。,如果A知道，会有什么不一样？,但是，链路状态协议就是为了保证不会出现这种情况。,A以为到F的最短路,E以为到F的最短路,会出现这种情况么？,不一定。因为链路状态的更新是需要时间的。更新完成以前就可能出现不一致。,最典型的例子就是链路失效。,链路发生失效后，E知道，而D不知道。,E以为到C的最短路是什么？,D以为到C的最短路是什么？,在D获知状态更新之前，目的为C的分组路由成环，延迟，丢失。,失效的快速恢复是前沿课题。,2009年春季图算法及其在通信网络中的应用,39/55,最短路算法,1,2,Label-Setting算法,Label-Correcting算法,Dijkstra算法只适用于正权重图，针对具有负权重（甚至负圈）的图，该怎么办？,2009年春季图算法及其在通信网络中的应用,40/55,Label-Correcting算法,负权重,1,2,3,5,一般的Label-Correcting,Bellman-Ford算法,应用,2009年春季图算法及其在通信网络中的应用,41/55,负权重,之所以FindMin得到的顶点可以被永久标记，因为该顶点的距离不可能被改进了。如果存在负权重，这个逻辑不再成立。,虽然通信网络中很少会出现负权重，但在其他问题中有可能。Algorithms in Java3rd ed。21.7节有这样一个例子。,如果不要求解必须为简单路径，那么不存在最短路。,如果要求解必须为简单路径，那么该问题是NP完全问题，与最长路问题一样难。,Label-Correcting算法就能达到这个目的。,Bellman-Ford算法是Label-Correcting算法的一个特例。,工程中，一般用Dijkstra算法（因为它快）；当出现负权重时，用Bellman-Ford算法。,2009年春季图算法及其在通信网络中的应用,42/55,Label-Correcting算法,负权重,1,2,3,5,一般的Label-Correcting,Bellman-Ford算法,应用,2009年春季图算法及其在通信网络中的应用,43/55,基本思想,必要性：如果所有距离标记等于最短路的距离，那么它们必然满足上述条件。,证明：如果d(j)大于d(i)+we，那么至少存在一条路径sij的距离小于d(j)。矛盾。,充分性：如果所有距离标记都满足上述条件，那么它们就是最短路的距离。,证明：任取一条P(sj)；该路径上的每条边都可以写出上述不等式；求和可知：d(j)是所有P(sj)的距离下限。,2009年春季图算法及其在通信网络中的应用,44/55,一般的Label-Correcting算法,正确性：该算法可以在有限步骤内收敛到最佳解。,复杂度：最坏复杂度为O(n2C)。,灵活性：可以用任意方式/顺序检查边，都能保证收敛。,但是：总得有个具体的方法吧。,况且：就没有复杂度更低的实现方法了么？,2009年春季图算法及其在通信网络中的应用,45/55,Label-Correcting算法,负权重,1,2,3,5,一般的Label-Correcting,Bellman-Ford算法,应用,2009年春季图算法及其在通信网络中的应用,46/55,FIFO实现(Bellman-Ford),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,v)时,d(v)d*(u)+we?,d(v)d*(u)+we?,k+1轮结束后，必有d(v)=d*(u)+we=d*(v),这不可能，因为与假设矛盾,2009年春季图算法及其在通信网络中的应用,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=,2009年春季图算法及其在通信网络中的应用,48/55,Label-Correcting算法,负权重,1,2,3,5,一般的Label-Correcting,Bellman-Ford算法,应用,2009年春季图算法及其在通信网络中的应用,49/55,应用：距离矢量路由协议,当i的反向邻接点发生了更新时。,当i 的正向邻接点到d 的距离发生了更新时。,CA,距离矢量更新消息,BA,AC,AB,CD,BC,BD,CB,DB,DC,这只是第1轮；每当路由器发生了更新，他就将其新的距离矢量发给他的邻接点(注意：不是洪泛)；直至没有更新为止。,2009年春季图算法及其在通信网络中的应用,50/55,最短路算法,1,2,Label-Setting算法,Label-Correcting算法,Dijkstra算法和Bellman-Ford算法解决的是单源最短路问题。那么，针对All-Pair最短路问题，是否存在更简单的算法？,2009年春季图算法及其在通信网络中的应用,51/55,重复最短路,假如使用的最短路算法复杂度为S(n,m,C)，则为O(nS(n,m,C)。,当然是Dijkstra好啰，因为它快嘛。,调用n遍Bellman-Ford呗，还能怎么办？,1遍Bellman-Ford加上(n 1)遍Dijkstra,第一次Bellman-Ford后，如果存在负圈，整个问题无解。如果没有负圈，对所有边进行如下权重变换：we(i,j)=we(i,j)+d(i)d(j),因为如果存在负圈，无论从哪个源点出发进行Bellman-Ford都能检测出来。,还因为利用得到的距离标记，可以将边的权重变换为非负值。,在新图上，从其它顶点出发分别调用1次Dijkstra算法。,2009年春季图算法及其在通信网络中的应用,52/55,All-Pair Label-Correcting,假定权重为整数，且最大值为C。,针对每个节点对，每轮需要进行n次三角操作。,最坏情况下，每轮只变小1（整数），故最多C轮。,总共多少节点对？,最多多少轮？,n2。,测试该不等式并更新称为三角操作。,2009年春季图算法及其在通信网络中的应用,53/55,Floyd-Warshall算法,因为该算法采用了一种非常聪明的，基于动态规划思想的三角操作方法。,2009年春季图算法及其在通信网络中的应用,54/55,小结（part 05）,End of Part 05,Trees and Flow,Rock&Roll!,