Dijkstra最短路径的算法思想南京大学课件.ppt

1、最短通路问题最短通路问题离散数学离散数学图论初步图论初步南京大学计算机科学与技术系南京大学计算机科学与技术系内容提要内容提要l引言引言lDijkstra算法算法l旅行商问题（旅行商问题（TSP）埃德斯数（埃德斯数（Erds number）Paul Erds(1913-1996),Hungary,U.S.A.,IsraelErds number 带权图与最短通路问题带权图与最短通路问题l带权图带权图：三元组：三元组(V,E,W)，(V,E)是图，是图，W是从是从E到到非负实数集的一个函数。非负实数集的一个函数。W(e)表示边表示边e的权。的权。l一条通路上所有边的权的和称为该通路的长度。一条通路

2、上所有边的权的和称为该通路的长度。l两点之间长度两点之间长度最小最小的通路称为两点之间的最短通路，的通路称为两点之间的最短通路，不一定是唯一的。不一定是唯一的。l单源点最短路问题单源点最短路问题 给定带权图给定带权图 G(V,E,W)，并指定一个源点，确定该，并指定一个源点，确定该源点到图中其它任一顶点的最短路（长度和路径）。源点到图中其它任一顶点的最短路（长度和路径）。Dijkstra最短路径的算法思想最短路径的算法思想(1959)l源点源点s到顶点到顶点v的最短路径若为的最短路径若为suv,则则su是是s到到u的最短路径。的最短路径。l(n-1)条最短路径按照其长度的非减次序求得，设它条最

3、短路径按照其长度的非减次序求得，设它们的相应端点分别为们的相应端点分别为u1,un-1，最短路径长度记为，最短路径长度记为d(s,ui)，i=1,n-1.l假设前假设前i条最短路径已知，第条最短路径已知，第(i+1)条最短路径长度：条最短路径长度：d(s,ui+1)=mind(s,uj)+W(uj,ui+1)|j=1,i求最短路径的求最短路径的Dijkstra算法算法l输入：连通带权图输入：连通带权图G，|VG|=n,指定顶点指定顶点s VGl输出：每个顶点输出：每个顶点v的标注的标注(L(v),u),其中：其中：lL(v)即从即从s到到v的最短路径长度（目前可得的）的最短路径长度（目前可得的

4、）lu是该路径上是该路径上v前一个顶点。前一个顶点。求最短路的一个例子求最短路的一个例子s77212412448353 4630bacdefgh求最短路的一个例子求最短路的一个例子s77212412448353 46301,c2,c8,c7,c4,cU1bacdefghs77212412448353 46301,c2,c8,c7,c4,cU2bacdefgh4,bS1s77212412448353 46301,c2,c8,c7,c4,cU3bacdefgh4,bS23,e6,es77212412448353 46301,c2,c8,c6,e4,cbacdefghU43,e9,hS3s77212

5、412448353 46301,c2,c8,c6,e4,cbacdefghU53,e9,hS46,d求最短路的一个例子求最短路的一个例子(续续)s77212312448353 46501266439求最短路的一个例子求最短路的一个例子(续续)s77212512448353 4630s77212312448353 465012664126433969Dijkstra算法的描述算法的描述1初始化：初始化：i=0,S0=s,L(s)=0,对其它一切对其它一切v VG,将将L(v)置为置为。若若n=1，结束。，结束。2 v Si=VG-Si,比较比较L(v)和和L(ui)+W(ui,v)的值的值(ui

6、 Si)如果如果L(ui)+W(ui,v)L(v),则将则将v的标注更新为的标注更新为(L(ui)+W(ui,v),ui)，即：即：L(v)=min L(v),minu SiL(u)+W(u,v)3.对所有对所有Si中的顶点，找出具有最小中的顶点，找出具有最小L(v)的顶点的顶点v,作为作为ui+14Si+1=Si ui+15.i=i+1;若若i=n-1,终止。否则：转到第终止。否则：转到第2步。步。Dijkstra算法的算法的分析分析l可终止性可终止性l计数控制计数控制l正确性正确性 需证明当算法终止时需证明当算法终止时lL(v)=d(s,v)对一切对一切v成立。成立。l由标记中的诸由标记中

7、的诸ui确定的路径是一条最短路径确定的路径是一条最短路径 (这里这里d(s,v)是是s到到v的最短路径长度，即距离。的最短路径长度，即距离。)l复杂性复杂性lO(n2)旅行商问题旅行商问题(Travelling Salesman Problem,TSP)ln个城市间均有道路，但距离不等，个城市间均有道路，但距离不等，旅行商从某地出发，走过旅行商从某地出发，走过其它其它n-1城市各一次，最后回到原地，城市各一次，最后回到原地，如何选择最短路线？如何选择最短路线？l数学模型：数学模型：l无向带权无向带权图图G：顶点对应于城市，边对应于城市之间的道顶点对应于城市，边对应于城市之间的道路，道路长度用相

8、应边的权表示。路，道路长度用相应边的权表示。l问题的解：权最小的哈密尔顿回路。问题的解：权最小的哈密尔顿回路。lG是带权完全图，总共有是带权完全图，总共有(n-1)!/2条哈密尔顿回路。因此，条哈密尔顿回路。因此，问题是如何从这问题是如何从这(n-1)!/2条中找出最短的一条。条中找出最短的一条。(含含25个顶点的完全图中不同的哈密尔顿回路有约个顶点的完全图中不同的哈密尔顿回路有约3.1 1023条，条，若机械地检查，每秒处理若机械地检查，每秒处理109条，需条，需1千万年。千万年。)旅行商问题旅行商问题l一个货郎（销售员）生活在城市一个货郎（销售员）生活在城市a，假定访问的城市，假定访问的城

9、市是是d,b,c，然后回到，然后回到a，求完成这次访问的最短路，求完成这次访问的最短路径径的的距离距离.1814bcad1110127旅行商问题旅行商问题l解：列出哈密尔顿回路解：列出哈密尔顿回路,并求其距离：并求其距离：（1）（）（abcda）=（12+7+11+18）=48 （2）（）（acbda）=（14+7+10+18）=49 （3）（）（abdca）=（12+10+11+14）=471814bcad1110127l哈密尔顿回路（路径）的最短路径问题哈密尔顿回路（路径）的最短路径问题！l下面介绍一种下面介绍一种最邻近算法最邻近算法：（1）选择任一顶点作为始点，找出离始点距离最小）选择任

10、一顶点作为始点，找出离始点距离最小的顶点，形成一条边的初始路径；的顶点，形成一条边的初始路径；（2）设）设u是最新加到这条路径上的是最新加到这条路径上的顶顶点，从不在这点，从不在这条路径上的所有条路径上的所有顶顶点中选择一个与点中选择一个与u距离最小的距离最小的顶顶点点,把连接把连接u与此结点的边加入路径中；重复执行与此结点的边加入路径中；重复执行直到直到G中的各中的各顶顶点均含在这条路径中。点均含在这条路径中。旅行商问题旅行商问题旅行商问题旅行商问题（3）把始点到最后加入的）把始点到最后加入的顶顶点的边放入路径中得到一点的边放入路径中得到一条哈密尔顿回路，并为近似最短的哈密尔顿回路条哈密尔顿回路，并为近似最短的哈密尔顿回路.1814bcad1110127旅行商问题旅行商问题(TSP)的研究进展的研究进展l（在最坏情况下）时间复杂性为多项式的算法？（在最坏情况下）时间复杂性为多项式的算法？l（在最坏情况下）时间复杂性为多项式的近似算法（在最坏情况下）时间复杂性为多项式的近似算法l保证保证:W W cW (c=3/2),误差为误差为50%l实际应用中，已有好的算法能够在几分钟内处理实际应用中，已有好的算法能够在几分钟内处理1000个节点的规模，误差在个节点的规模，误差在2%。作业作业l教材教材9.6lp.507:6,21,22,25