最短路算法(图论)

图算法及其在通信网中的应用图算法及其在通信网中的应用王晟王晟 博士 教授 博导Part 05: 最短路算法最短路算法2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用2 / 55最短路算法最短路算法12Label-Setting算法算法 Label-Correcting算法算法 毫无疑问，重点将是以毫无疑问，重点将是以Dijkstra算法为代表的算法为代表的Label-Setting算法。算法。3All-Pair最短路算法最短路算法 2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用3 / 55Label-Setting算法算法4基本Dijkstra算法1235分析(Analysis)扩展(Extension)加速(Speed up)应用(Application)2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用4 / 55基本基本Dijkstra算法算法Dijkstra算法是本课程的核心内容，务必要掌握其思想和具体的编程方法。算法是本课程的核心内容，务必要掌握其思想和具体的编程方法。问题分析问题分析代码设计代码设计算法示例算法示例求解思路求解思路伪码描述伪码描述Dijkstra算法算法2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用5 / 55问题描述问题描述 单源最短路问题单源最短路问题给定有向加权图给定有向加权图G(V, E)，给定源点，给定源点/起始点起始点s，求，求从从s出发到出发到V中其它所有顶点的权重最小的路径。中其它所有顶点的权重最小的路径。所有这些最短路构成的是一个怎样的子图？所有这些最短路构成的是一个怎样的子图？树树最短路径树最短路径树假设假设1)权重为正整数权重为正整数;2)连通图连通图;3)存在多条最短路存在多条最短路时时,只求只求1条条.为什么一定是树？为什么一定是树？最短路上的子路径也是最短路最短路上的子路径也是最短路最短路径树是生成树么？最短路径树是生成树么？是的是的最短路径树是最小生成树么？最短路径树是最小生成树么？不一定不一定ASBC11221ASBC122ASBC1212009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用6 / 55Dijkstra的求解思路的求解思路算法思路算法思路逐步地发展最短路径逐步地发展最短路径树，直至它覆盖所有树，直至它覆盖所有顶点。顶点。怎样实现？怎样实现？构造一个循环，每次构造一个循环，每次循环都增加一个顶点循环都增加一个顶点到最短路径树上。到最短路径树上。加哪个顶点？加哪个顶点？从所有与树邻接的顶从所有与树邻接的顶点中，选择离源点最点中，选择离源点最近的。近的。怎么知道谁最近？怎么知道谁最近？对每个顶点，都用一对每个顶点，都用一个距离标记个距离标记(Label)来记录。来记录。哪里来的距离标记？哪里来的距离标记？每次循环都需要对距每次循环都需要对距离标记进行更新。离标记进行更新。如何维护最短路径树？如何维护最短路径树？如何选择顶点？如何选择顶点？如何更新距离标记？如何更新距离标记？树上顶点的集合树上顶点的集合S。顶点的前继顶点的前继p(i)。FindMin()Update(i)2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用7 / 55伪码描述伪码描述DijkstraAlg (G(V, E), s)FOR all vertex j in V DO d(j) = ; p(j) = NULL;S = s; d(s) = 0; p(s) = NULL; Update(s);WHILE S V DO i = FindMin(); S = S U i; Update(i);END WHILEUpdate ( i )FOR each edge e incident to i DO IF e.weight + d(i) d(e.head) THEN d(e.head) = e.weight + d(i); p(e.head) = i; END IFEND FORFindMin ()Find vertex v in V S which has minimum d(v);RETURN v;d(j): 顶点顶点j的距离标记。的距离标记。p(j): 顶点顶点j在最短路径树上的前继点。在最短路径树上的前继点。S: 最短路径树上的顶点集合。最短路径树上的顶点集合。2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用8 / 55怎样根据得到的这些信息重构出最短路径？怎样根据得到的这些信息重构出最短路径？Dijkstra算法示例算法示例 saedbc241423322 0cs2,s4,sDijkstraAlg (G(V, E), s)FOR all vertex j in V DO d(j) = ; p(j) = NULL;S = s; d(s) = 0; p(s) = NULL; Update(s);WHILE S V DO i = FindMin(); S = S U i; Update(i);END WHILEUpdate ( i )FOR each edge e incident to i DO IF e.weight + d(i) d(e.head) THEN d(e.head) = e.weight + d(i); p(e.head) = i; END IFEND FORFindMin ()Find vertex v in V S which has minimum d(v);RETURN v;StepSd(a), p(a)d(b), p(b)d(c), p(c)d(d), p(d)d(e), p(e)012345ssasaesaedsaedbsaedbc2, s2, s 6, a6, a6, a6, a 6, d6, d6, d 4, a4, a4, a4, s3, a3, aa6,a4,a3,aed6,db 每条边被检查了每条边被检查了(被描黑被描黑)几次？几次？如果放松如果放松“连通图连通图”假设，如何改进代码？假设，如何改进代码？2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用9 / 55Dijkstra算法代码设计算法代码设计 DijkstraAlg d(j)和和p(j) 如何管理如何管理 FindMin Update从伪码到从伪码到代码代码 如何实现如何实现d(j)和和p(j)Option 1：单独用数组：单独用数组/vector来实现；来实现； Option 2：创建一个：创建一个CVertex类来记录；类来记录； 思路思路 两个方法都可以；两个方法都可以； 使用类便于扩展，也便于封装。使用类便于扩展，也便于封装。 细节细节 构造函数？构造函数？ 接口函数？接口函数？代码设计代码设计在在CGraph中增加一个中增加一个CVertex的的map创建一个创建一个CVertex类类在在CGraph中增加一个中增加一个DijkstraAlg函数函数用一个用一个list来实现暂时标记的顶点集合来实现暂时标记的顶点集合为每个顶点准备一个为每个顶点准备一个CEdge的的list 如何管理这些如何管理这些CVertex对象？对象？l Q 1：用什么数据结构？：用什么数据结构？l Q 2：这个数据结构放在哪里？：这个数据结构放在哪里？ 思路思路 用一个用一个map，以，以ID为为key； 放在放在CGraph里面。里面。 细节细节 如何初始化？如何初始化？ 什么时候需要查询什么时候需要查询/访问？访问？ DijkstraAlg函数放在哪里？函数放在哪里？l option 1：作为一个独立的函数：作为一个独立的函数l option 2：作为：作为CGraph的成员函数的成员函数 思路思路 两种都可以，但前者需要传入图对象；两种都可以，但前者需要传入图对象； 为了方便，我们放在为了方便，我们放在CGraph里。里。 细节细节 使用了哪些使用了哪些CGraph里的成员变量？里的成员变量？ 如何设计输出？如何设计输出？ 如何实现如何实现FindMin？物理意义：从暂时标记顶点集合（物理意义：从暂时标记顶点集合（V S）中找出距离标记最小的顶点。中找出距离标记最小的顶点。 思路思路 用一个用一个list来实现暂时标记顶点集合；来实现暂时标记顶点集合； 用用sort来实现对来实现对list的排序。的排序。 细节细节 如何更改循环判决条件？如何更改循环判决条件？ list的的sort需要能对对象实现比较判决。需要能对对象实现比较判决。 如何实现如何实现Update？物理意义：给定一个顶点，逐一检查物理意义：给定一个顶点，逐一检查/遍历遍历与它关联的边。与它关联的边。 思路思路 为每个顶点准备一个记录关联边的为每个顶点准备一个记录关联边的list； 遍历并检查对应的顶点是否需要更新。遍历并检查对应的顶点是否需要更新。 细节细节 在在CGraph里存储这个数据结构？里存储这个数据结构？ 顶点顶点边边顶点的操作细节。顶点的操作细节。2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用10 / 55DijkstraAlg源码源码(一一)class CGraph private:int numVertex, numEdge;list IncidentList; / 所有的边所有的边map mapVID_Vertex; / 所有的顶点所有的顶点list listTempMark; / 暂时标记的顶点集合暂时标记的顶点集合mapint, list mapVID_listEdge; / 记录与顶点关联的出度边记录与顶点关联的出度边Update(int VID); public:CGraph(char* inputFile);CGraph(list listEdge);CGraph(CGraph &);CGraph();int getNumVertex();int getNumEdge();DijkstraAlg(int VID);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 / 55DijkstraAlg源码源码(二二)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 / 55Label-Setting算法算法4基本Dijkstra算法1235分析(Analysis)扩展(Extension)加速(Speed up)应用(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，OF COURSEYES，IT IS.sS集合集合2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用15 / 55复杂度分析复杂度分析DijkstraAlg (G(V, E), s)FOR all vertex j in V DO d(j) = ; p(j) = NULL;S = s; d(s) = 0; p(s) = NULL; Update(s);WHILE S V DO i = FindMin(); S = S U i; Update(i);END WHILE有几个循环？有几个循环？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)加速(Speed up)应用(Application)2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用17 / 55扩展扩展(Extension)针对不同问题的物理意义，通过扩展针对不同问题的物理意义，通过扩展Dijkstra算法来达到求解目的。算法来达到求解目的。单源单宿最短路问题单源单宿最短路问题最短分离路径对问题最短分离路径对问题带宽约束最短路问题带宽约束最短路问题最大通过率路径问题最大通过率路径问题Dijkstra算法算法扩展扩展2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用18 / 55单源单宿最短路单源单宿最短路 单源单宿最短路问题单源单宿最短路问题给定加权图给定加权图G，并给定顶点，并给定顶点s和和d，求从，求从s到到d的最小权重路径。的最小权重路径。如何修改如何修改Dijkstra算法来求解这个问题？算法来求解这个问题？增加一个判断分支，永久标记增加一个判断分支，永久标记d时，停止循环。时，停止循环。怎样实现？怎样实现？重载一个重载一个2参数的参数的DijkstraAlg函数。函数。这个算法的复杂度是多少？这个算法的复杂度是多少？仍然是仍然是O(n2)。Project No.2-1给出求解单源单宿问题的代码。要求设计一个给出求解单源单宿问题的代码。要求设计一个CPath类，从类，从Dijkstra计算计算得到的得到的CVertex中重构出一个中重构出一个CPath对象，并输出。对象，并输出。2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用19 / 55最大通过率路径最大通过率路径最大通过率路径问题最大通过率路径问题给定加权图给定加权图G，边上权重表示业务流经该边时的通过比例（大于，边上权重表示业务流经该边时的通过比例（大于0小于小于1）。给定源点。给定源点s，求从，求从s出发到其他顶点的最大通过率路径。出发到其他顶点的最大通过率路径。Project No.2-2给定加权图给定加权图G，边上权重代表通过率。给定顶点，边上权重代表通过率。给定顶点s，求从，求从s出发到其他顶点出发到其他顶点的最大通过率路径。的最大通过率路径。路径通过率与边的通过率是什么关系？路径通过率与边的通过率是什么关系？乘性关系。乘性关系。怎样实现？怎样实现？修改修改update函数。函数。修改权重，然后调用修改权重，然后调用DijkstraAlg。2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用20 / 55带宽约束下的最短路带宽约束下的最短路带宽约束下的最短路问题带宽约束下的最短路问题给定加权图给定加权图G，每条边上既有权重，也有，每条边上既有权重，也有capacity。给定源点。给定源点s，以及带，以及带宽需求宽需求C。求从。求从s出发到其他顶点的带宽大于出发到其他顶点的带宽大于C的最小权重路径。的最小权重路径。求解思路？求解思路？先删除先删除capacity小于小于C的边，然后在这个新的图上调用的边，然后在这个新的图上调用DijkstraAlg。怎样实现？怎样实现？需要遍历所有的边，即需要遍历所有的边，即IncidentList。根据根据IncidentList求求mapVID_listEdge，然后调用，然后调用DijkstraAlg。Project No.2-3给出求解带宽约束最短路问题的代码。要求设计一个给出求解带宽约束最短路问题的代码。要求设计一个CGraph的成员函数的成员函数来实现边的删除。来实现边的删除。2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用21 / 55最短分离路径对最短分离路径对(Shortest Disjoint Path Pair)最短分离路径对问题最短分离路径对问题给定加权图给定加权图G。给定源点。给定源点s和宿点和宿点d。求从。求从s出发到出发到d的一对路径（两条）的一对路径（两条），要求这两条路径，要求这两条路径“链路分离链路分离”，且路径权重之和最小。，且路径权重之和最小。Nave Idea 在在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)加速(Speed up)应用(Application)2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用23 / 55加速加速(Speed up)本课程略去了利用各种本课程略去了利用各种“堆堆”数据结构来实现数据结构来实现Dijkstra算法加速的内容。着算法加速的内容。着重讲一种理论上有效（且有趣）的加速方法，以及两种现实中很有效的方法重讲一种理论上有效（且有趣）的加速方法，以及两种现实中很有效的方法。Dial实现实现A*算法算法双向双向Dijkstra算法算法Dijkstra算法算法加速加速2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用24 / 55Dial实现实现通过降低通过降低FindMin的复杂度来加速的复杂度来加速目的目的Bucket(k) = i i V, d(i) = k 方法方法令令C表示最大的权重，则距离标记最大为表示最大的权重，则距离标记最大为nC。换。换句话说，最多句话说，最多nC个桶，个桶，FindMin复杂度为复杂度为O(nC)。性能性能每次每次Update时，也需要更新桶。时，也需要更新桶。更新更新2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用25 / 55Dijkstra算法的算法的Dial实现实现 saedbc241423322 0cs2,s4,sDijkstraAlg (G(V, E), s)FOR all vertex j in V DO d(j) = ; p(j) = NULL;S = s; d(s) = 0; p(s) = NULL; Update(s);WHILE S V DO i = FindMin(); S = S U i; Update(i);END WHILEStepSd(a), p(a)d(b), p(b)d(c), p(c)d(d), p(d)d(e), p(e)012345ssasaesaedsaedbsaedbc2, s2, s 6, a6, a6, a6, a 6, d6, d6, d 4, a4, a4, a4, s3, a3, aa6,a4,a3,aed6,db 01234567= nC = 24abc d eaebdec2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用26 / 55实现细节提示实现细节提示Dial算法实现难点算法实现难点难点难点1：基于桶的：基于桶的FindMin难点难点2：桶的更新：桶的更新/桶的实现：桶的实现：mapint,map mapBuckets;内层的内层的map的的key是顶点是顶点ID。该。该map代表单个的桶。代表单个的桶。外层的外层的map的的key是距离标记。该是距离标记。该map代表所有的桶。代表所有的桶。/指向桶的迭代器指向桶的迭代器mapint,map :iterator itBucket;FindMin中，用于指向具体的桶。中，用于指向具体的桶。递增该迭代器，直至对应的桶的递增该迭代器，直至对应的桶的empty函数返回函数返回FALSE。Hint 1Hint 2Hint 3Update时，如果某个顶点的距离标记从时，如果某个顶点的距离标记从x变到了变到了y，先根据，先根据x查找查找mapBuckets再根据其再根据其ID定位到它在内层定位到它在内层map中的位置，然后取出该顶点。中的位置，然后取出该顶点。根据根据y找到新的桶的位置，做一个找到新的桶的位置，做一个pair，把它插入这个桶。，把它插入这个桶。2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用27 / 55加速加速(Speed up)本课程略去了利用各种本课程略去了利用各种“堆堆”数据结构来实现数据结构来实现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), for all u SF, v SB上述路径中具有最小权重的路径作为输出。上述路径中具有最小权重的路径作为输出。比较比较只要不是给定的宿点，都不必要。只要不是给定的宿点，都不必要。SF表示正向算法中的永久标记顶点集合。表示正向算法中的永久标记顶点集合。e(u,v)表示从顶点表示从顶点u到到v的一条有向边。的一条有向边。SB表示反向算法中的永久标记顶点集合。表示反向算法中的永久标记顶点集合。P(x,y)表示从表示从x到到y的最短路径。的最短路径。为什么要进行这样的比较？为什么要进行这样的比较？说明：说明：ascb53242d2交集为交集为c，但，但sacd的距离大的距离大于于sabd2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用30 / 55实现细节提示实现细节提示双向双向Dijkstra实现难点实现难点难点难点1：要改变循环体。：要改变循环体。难点难点3：拼凑和比较。：拼凑和比较。难点难点2：要增加数据结构。：要增加数据结构。Hint 1循环的终止条件为某个顶点被两个方向都永久标记。循环的终止条件为某个顶点被两个方向都永久标记。循环体中要同时进行两个方向的循环体中要同时进行两个方向的FindMin和和Update。Hint 2CVertex中要记录两个方向的距离和前继。中要记录两个方向的距离和前继。CGraph中要增加中要增加mapVID_listRevEdge。Hint 3逐一检查逐一检查SF中的顶点，看他的邻接点是否在中的顶点，看他的邻接点是否在SB中。中。如果存在，就重构出一条完整的路径如果存在，就重构出一条完整的路径p(从从s到到d)，放入一个，放入一个list中。中。对这个对这个list排序，然后输出第一个元素。排序，然后输出第一个元素。2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用31 / 55研究性研究性Project 自己设计实验，并通过大量实验结果来得出自己设计实验，并通过大量实验结果来得出你的结论。你的结论。 提交提交研究报告研究报告。包括问题的描述；求解方法。包括问题的描述；求解方法的描述；实验设计思路；结果分析；结论；改的描述；实验设计思路；结果分析；结论；改进实验的方向等。进实验的方向等。研究性研究性Project的要求的要求研究性研究性Project No. R1下面两项任选一项：下面两项任选一项：A）对比）对比/定量研究定量研究Dijkstra算法和算法和Dial算法的性能。算法的性能。B）对比）对比/定量研究定量研究Dijkstra算法和双向算法和双向Dijkstra算法的性能。算法的性能。2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用32 / 55加速加速(Speed up)本课程略去了利用各种本课程略去了利用各种“堆堆”数据结构来实现数据结构来实现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)加速(Speed up)应用(Application)2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用35 / 55应用：链路状态路由协议应用：链路状态路由协议OSPF(Open Shortest Path First)协议是协议是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序号序号时间时间4553链路状态信息的产生链路状态信息的产生链路状态信息的洪泛链路状态信息的洪泛拓扑图的构造拓扑图的构造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负权重有什么用？负权重有什么用？虽然通信网络中很少会出现负权重，但在其他虽然通信网络中很少会出现负权重，但在其他问题中有可能。问题中有可能。Algorithms in Java3rd ed。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)FOR all vertex j in V DO d(j) = ; p(j) = NULL;END FORd(s) = 0; p(s) = NULL; WHILE some e(i,j) satisfies d(j)d(i)+we DO d(j) = d(i) + we; p(j) = i;END WHILE分析分析负圈负圈实现实现正确性：正确性： 该算法可以在有限步骤内收敛到最佳解。复杂度：复杂度： 最坏复杂度为O(n2C)。怎么检测负圈？怎么检测负圈？ 如果某个距离标记小于等于nC时，必然存在负圈。灵活性：灵活性： 可以用任意方式/顺序检查边，都能保证收敛。但是：但是： 总得有个具体的方法吧。况且：况且： 就没有复杂度更低的实现方法了么？2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用45 / 55Label-Correcting算法算法负权重负权重1235一般的一般的Label-CorrectingBellman-Ford算法算法应用应用2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用46 / 55FIFO实现实现(Bellman-Ford)算法描述算法描述 算法由算法由n次循环构成。次循环构成。 每次循环都遍历所有的每次循环都遍历所有的m条边，发现某条边不满条边，发现某条边不满足最优性条件，就更新。足最优性条件，就更新。 如果第如果第n次循环还有更新，次循环还有更新，说明有负圈。说明有负圈。为什么为什么n次循环就够了？为什么第次循环就够了？为什么第n次有更新就说明存在负圈？次有更新就说明存在负圈？1）s到任一其他顶点的最短路径最多到任一其他顶点的最短路径最多n 1跳（即经过跳（即经过n 1条边）。条边）。除非存在负圈。除非存在负圈。2）假如）假如s到到j实际上的最短路有实际上的最短路有k跳，那么跳，那么k轮循环后，轮循环后，d(j)必然会必然会被更新为被更新为d*(j)。d*(x)表示表示s到到x的最短路的距离。的最短路的距离。上述事实意味着，该算法最多经过上述事实意味着，该算法最多经过n 1轮循环就可以保证所有的轮循环就可以保证所有的距离标记都更新为最佳值。除非存在负圈。距离标记都更新为最佳值。除非存在负圈。k=1第一次循环第一次循环(k=1)后后，具有最短路跳数为，具有最短路跳数为1的那些顶点的距离的那些顶点的距离标记会被更新为最佳标记会被更新为最佳值么？值么？YES，OF COURSEkk+1假定第假定第k次循环后，次循环后，所有具有最短路跳数所有具有最短路跳数小于等于小于等于k的那些顶的那些顶点标记都被更新为最点标记都被更新为最佳值了。问佳值了。问k+1次循次循环后，还是这样么？环后，还是这样么？YES，IT IS.usvk k跳跳k+1k+1跳跳k k轮后，必有轮后，必有d(u)=dd(u)=d* *(u)(u)k+1k+1轮检查轮检查e(u,v)e(u,v)时时d(v) d(v) d d* *(u)+w(u)+we e? ?d(v) dd(v) d(i)+we DO d(j) = d(i) + we; p(j) = i; 若若j LIST就插入就插入LIST；END WHILE 一次循环中，不必检查所有的边。一次循环中，不必检查所有的边。 上一轮中没有更新的顶点所上一轮中没有更新的顶点所“发出发出”的边都不必检查。的边都不必检查。 不需要不需要 n 轮循环。轮循环。 只要能检测出某一轮中没有更新距离只要能检测出某一轮中没有更新距离标记，就可以终止循环。标记，就可以终止循环。 除非存在负圈。除非存在负圈。0LIST = s 3LIST = LIST = a6LIST = af3LIST = afeLIST = fe5LIST = feb4LIST = eb6LIST = ebdLIST = bdLIST = dLIST = 2LIST = e9LIST = ecLIST = cLIST = 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后，如后，如果存在负圈，整个问题无解。果存在负圈，整个问题无解。如果没有负圈，对所有边进行如果没有负圈，对所有边进行如下权重变换：如下权重变换：we(i,j) = we(i,j) + d(i) d(j)这怎么可能？这怎么可能？因为如果存在负圈，无论从哪个源点出发进行因为如果存在负圈，无论从哪个源点出发进行Bellman-Ford都都能检测出来。能检测出来。还因为利用得到的距离标记，可以将边的权重变换为非负值。还因为利用得到的距离标记，可以将边的权重变换为非负值。 在新图上，从其它顶点出发在新图上，从其它顶点出发分别调用分别调用1次次Dijkstra算法。算法。asbd(b)d(a)w2009年春季年春季图算法及其在通信网络中的应用图算法及其在通信网络中的应用52 / 55All-Pair Label-Correcting最优性条件最优性条件令令d(i,j)表示从顶点表示从顶点i 到顶到顶点点j 的距离标记。共有的距离标记。共有n2个这样的标记。所有这些