最短路算法(图论)ppt课件.ppt

《最短路算法(图论)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图算法及其在通信网中的应用王晟博士教授博导Part05:最短路算法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基本Dijks

2、tra算法Dijkstra算法是本课程的核心内容，务必要掌握其思想和具体的编程方法。问题分析代码设计算法示例求解思路伪码描述Dijkstra算法2009年春季图算法及其在通信网络中的应用5/55问题描述单源最短路问题给定有向加权图G(V,E)，给定源点/起始点s，求从s出发到V中其它所有顶点的权重最小的路径。所有这些最短路构成的是一个怎样的子图？树最短路径树假设权重为正整数;连通图;存在多条最短路时,只求1条.为什么一定是树？最短路上的子路径也是最短路最短路径树是生成树么？是的最短路径树是最小生成树么？不一定ASBC11221ASBC122ASBC1212009年春季图算法及

3、其在通信网络中的应用6/55Dijkstra的求解思路算法思路逐步地发展最短路径树，直至它覆盖所有顶点。怎样实现？构造一个循环，每次循环都增加一个顶点到最短路径树上。加哪个顶点？从所有与树邻接的顶点中，选择离源点最近的。怎么知道谁最近？对每个顶点，都用一个距离标记(Label)来记录。哪里来的距离标记？每次循环都需要对距离标记进行更新。如何维护最短路径树？如何选择顶点？如何更新距离标记？树上顶点的集合S。顶点的前继p(i)。FindMin()Update(i)2009年春季图算法及其在通信网络中的应用7/55伪码描述DijkstraAlg(G(V,E),s)FORallvert

4、exjinVDOd(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)

5、最短路径树上的前继点。S:最短路径树上的顶点集合。2009年春季图算法及其在通信网络中的应用8/55怎样根据得到的这些信息重构出最短路径？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

6、+d(i)

7、何改进代码？2009年春季图算法及其在通信网络中的应用9/55Dijkstra算法代码设计DijkstraAlgd(j)和p(j)如何管理FindMinUpdate从伪码到代码如何实现d(j)和p(j)Option1：单独用数组/vector来实现；Option2：创建一个CVertex类来记录；思路两个方法都可以；使用类便于扩展，也便于封装。细节构造函数？接口函数？代码设计在CGraph中增加一个CVertex的map创建一个CVertex类在CGraph中增加一个DijkstraAlg函