05-最短路算法-XXXX-BIG

通信网络理论基础王晟博士教授博导Part05:最短路算法2014年春季通信网络理论基础2/70最短路算法12Label-Setting算法Label-Correcting算法毫无疑问，重点将是以Dijkstra算法为代表的Label-Setting算法。3All-Pair最短路算法3/70Label-Setting算法4基本Dijkstra算法1235分析(Analysis)扩展(Extension)加速(Speedup)应用(Application)2014年春季通信网络理论基础4/70基本Dijkstra算法Dijkstra算法是本课程的核心内容，务必要掌握其思想和具体的编程方法。问题分析代码设计算法示例求解思路伪码描述Dijkstra算法2014年春季通信网络理论基础问题描述5/70单源最短路问题给定有向加权图G(V,E)，给定源点/起始点s，求从s出发到V中其它所有顶点的权重最小的路径。所有这些最短路构成的是一个怎样的子图？树最短路径树假设1)权重为正整数;2)连通图;3)存在多条最短路时,只求1条.为什么一定是树？最短路上的子路径也是最短路2014年春季通信网络理论基础最短路径树6/70最短路径树是生成树么？是的最短路径树是最小生成树么？不一定ASBC11221ASBC122ASBC1212014年春季通信网络理论基础7/70Dijkstra的求解思路算法思路逐步地发展最短路径树，直至它覆盖所有顶点。怎样实现？构造一个循环，每次循环都增加一个顶点到最短路径树上。加*个顶点？从所有与树邻接的顶点中，选择离源点最近的。**知道谁最近？对每个顶点，都用一个距离标记(Label)来记录。距离标记？每次循环都需要对距离标记进行更新。如何维护最短路径树？如何选择顶点？如何更新距离标记？树上顶点的集合S。顶点的前继p(i)。FindMin()Update(i)2014年春季通信网络理论基础8/70伪码描述DijkstraAlg(G(V,E),s)FORallvertexjinVDOd(j)=;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILESVDOi=FindMin();S=SU{i};Update(i);ENDWHILEUpdate(i)FOReachedgeeincidenttoiDOIFe.weight+d(i)d(e.head)d(e.head)=e.weight+d(i);p(e.head)=i;ENDIFENDFORFindMin()FindvertexvinV–Swhichhasminimumd(v);RETURNv;d(j):顶点j的距离标记。p(j):顶点j在最短路径树上的前继点。S:最短路径树上的顶点集合。2014年春季通信网络理论基础9/70怎样根据得到的这些信息重构出最短路径？Dijkstra算法示例saedbc2414233220cs2,s4,sDijkstraAlg(G(V,E),s)FORallvertexjinVDOd(j)=;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILESVDOi=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,s6,a6,a6,a6,a6,d6,d6,d4,a4,a4,a4,s3,a3,aa6,a4,a3,aed6,db每条边被检查了(被描黑)几次？如果放松“连通图”假设，如何改进代码？2014年春季通信网络理论基础10/70Dijkstra算法代码设计d(j)和p(j)从伪码到代码如何实现d(j)和p(j)Option1：单独用数组/vector来实现；Option2：创建一个CVertex类来记录；思路•两个方法都可以；•使用类便于扩展和封装。细节•构造函数？•接口函数？代码设计创建一个CVertex类2014年春季通信网络理论基础11/70Dijkstra算法代码设计d(j)和p(j)如何管理从伪码到代码代码设计在CGraph中增加一个CVertex的map创建一个CVertex类如何管理这些CVertex对象？Q1：用什么数据结构？Q2：这个数据结构放在*里？思路•用一个map，以ID为key；•放在CGraph里面。细节•如何初始化？•什么时候需要查询/访问？2014年春季通信网络理论基础12/70Dijkstra算法代码设计DijkstraAlgd(j)和p(j)如何管理从伪码到代码代码设计在CGraph中增加一个CVertex的map创建一个CVertex类在CGraph中增加一个DijkstraAlg函数DijkstraAlg函数放在*里？option1：作为一个**的函数option2：作为CGraph的成员函数思路•两种都可以，但前者需要传入图对象；•为了方便，放在CGraph里。细节•使用了*些CGraph里的成员变量？•如何设计输出？2014年春季通信网络理论基础13/70Dijkstra算法代码设计DijkstraAlgd(j)和p(j)如何管理FindMin从伪码到代码代码设计在CGraph中增加一个CVertex的map创建一个CVertex类在CGraph中增加一个DijkstraAlg函数用一个list来实现暂时标记的顶点集合如何实现FindMin？物理意义：从暂时标记顶点集合（V–S）中找出距离标记最小的顶点。思路•用一个list来实现暂时标记顶点集合；•用sort来实现对list的排序。细节•如何更改循环判决条件？•list的sort需要能对对象实现比较判决。2014年春季通信网络理论基础14/70Dijkstra算法代码设计DijkstraAlgd(j)和p(j)如何管理FindMinUpdate从伪码到代码代码设计在CGraph中增加一个CVertex的map创建一个CVertex类在CGraph中增加一个DijkstraAlg函数用一个list来实现暂时标记的顶点集合为每个顶点准备一个CEdge的list如何实现Update？物理意义：给定一个顶点，逐一检查/遍历与它关联的边。思路•为每个顶点准备一个记录关联边的list；•遍历并检查对应的顶点是否需要更新。细节•CGraph里存储这个数据结构？•顶点边顶点的操作细节。2014年春季通信网络理论基础代码：CGraph类15/70classCGraph{private:intnumVertex,numEdge;listCEdge*IncidentList;//所有的顶点mapint,CVertex*mapVID_Vertex;//暂时标记的顶点集合listCVertex*listTempMark;//记录与顶点关联的出度边mapint,listCEdge*mapVID_listEdge;Update(intVID);public:CGraph(char*inputFile);CGraph(listCEdge*listEdge);CGraph(CGraph&);~CGraph();intgetNumVertex();intgetNumEdge();DijkstraAlg(intVID);};2014年春季通信网络理论基础代码：Cvertex类16/70classCVertex{public:intd;intp;intID;CVertex(){d=INFINITY;p=NULL;}~CVertex();};boolpVertexComp(CVertex*x,CVertex*y){if(x-dy-d)returnTRUE;returnFALSE;};如果sort的是对象本身，可以用重载来实现。这里sort的是对象指针，所以写了个外部函数。2014年春季通信网络理论基础代码：DijkstraAlg17/70voidCGraph::DijkstraAlg(ints){mapint,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);}}2014年春季通信网络理论基础代码：Update18/70voidCGraph::Update(intv){listCEdge*lEdge=mapVID_listEdge[v];listCEdge*::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+wh-d){h-d=t-d+w;h-p=v;}}}2014年春季通信网络理论基础19/70Label-Setting算法4基本Dijkstra算法1235分析(Analysis)扩展(Extension)加速(Speedup)应用(Application)2014年春季通信网络理论基础20/70分析(Analysis)正确性分析和复杂度分析是算法分析中两个主要的内容。复杂度分析正确性分析Dijkstra算法分析2014年春季通信网络理论基础21/70正确性分析kk+1问题变化问题1：Dijkstra算法求出的是从s到其他顶点的最短路么？k=1第一次循环(k=1)时，Dijkstra算法求出的路径***？它是从s出发的最短路么？假定第k次循环求得了第k条最短路，问第k+1次循环求得的是第k+1短的路径么？问题2：Dijkstra算法求出的是从s出发的前n条最短路(宿点必须不同)么？YES，OFCOURSEYES，ITIS.sS集合2014年春季通信网络理论基础22/70复杂度分析DijkstraAlg(G(V,E),s)FORallvertexjinVDOd(j)=;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILESVDOi=FindMin();S=SU{i};Update(i);ENDWHILE有几个循环？2FOR循环的操作次数？2nWHILE循环了几次？nWHILE循环的操作次数呢？FindMin•从n个数中求最小，复杂度为n；•n+(n-1)+…+1n(n-1)/2Update•每次循环检查的边的数目都不同；•但是都不重复；•总共检查了m次总的操作次数为：2n+n(n-1)/2+n+m结论：Dijkstra算法的复杂度为O(n2)2014年春季通信网络理论基础23/70Label-Setting算法4基本Dijkstra算法1235分析(Analysis)扩展(Extension)加速(Speedup)应用(Application)**