DS图最短路径实用教案

1、7.6 最短路径(ljng) 所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达(dod)另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。 BAEDC105030101002060A到到E的路径的路径(ljng)有：有：AE：100ADE：90 ADCE：60 ABCE：701.单源点最短路径2.所有顶点对之间的最短路径第1页/共20页第一页，共21页。问题描述：给定带权有向图G(V, E)和源点vV，求从v到G中其余各顶点(dngdin)的最短路径。 单源点最短路径(ljng)问题 应用(yngyng)实例计算机网络传输的问题：怎样找到

2、一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法Dijkstra算法。Edsger Dijkstra（1930-2002）经典之作：“GoTo Statement Considered Harmful”。 1972年因发明ALGOL语言而获得图灵奖，获奖演说是“The Humble Programmer”。 在操作系统中，提出了PV操作；第2页/共20页第二页，共21页。基本思想：设置一个集合S 存放已经找到最短路径的顶点，S 的初始状态只包含源点v，对vi V-S，假设从源点v到vi 的有向边为最短

3、路径。以后每求得一条最短路径v, , vk，就将vk 加入集合S中，并将路径v, , vk , vi与原来的假设相比较，取路径长度(chngd)较小者为最短路径。重复上述过程，直到集合V 中全部顶点加入到集合S 中。Dijkstra算法(sun f)第3页/共20页第三页，共21页。 集集 合合 V - -S集集合合 SvvixDijkstra算法(sun f)的基本思想假设 S为已求得最短路径的终点的集合，则可证明：下一条最短路径(设其终点为x)或者是弧(v，x)，或者是中间只经过S中的顶点而最后到达顶点x的路径。这可用反证法来证明。假设此路径上有一个顶点不在S中，则说明存在一条终点不在S而

4、长度比此路径短的路径。但是，这是不可能的。因为我们是按路径长度递增的次序来产生(chnshng)各最短路径的，即长度比此路径短的所有路径均己产生(chnshng)，它们的终点必定在S中，即假设不成立。 第4页/共20页第四页，共21页。ABAEDC105030101002060S=AAB:(A, B)10AC:(A, C)AD: (A, D)30AE: (A, E)100ABAEDC105030101002060S=A, BAB:(A, B)10AC:(A, B, C)60AD: (A, D)30AE: (A, E)100B第5页/共20页第五页，共21页。ABAEDC105030101002

5、060S=A, BAB:(A, B)10AC:(A, B, C)60AD: (A, D)30AE: (A, E)100BABAEDC105030101002060S=A, B, DAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, E)90BD第6页/共20页第六页，共21页。ABAEDC105030101002060S=A, B, DAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, E)90BDABAEDC105030101002060S=A, B, D, CAB:(A, B)10AC:(A, D, C

6、)50AD: (A, D)30AE: (A, D, C, E)60BDC第7页/共20页第七页，共21页。ABAEDC105030101002060S=A, B, D, C, EAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E)60BDCE第8页/共20页第八页，共21页。 例：给定(i dn)带权有向图G和源点v, 求从v到G中其余各顶点的最短路径。V5V0V2V4V1V310030010601020505V0V2V4V3V5V0始点始点 终点终点(zhngdin) Di 最短路径最短路径V1V2V3V4 V51030100103010

7、0106030100106030100105030100(V0, V2)(V0, V4)(V0, V5)(V0, V2)(V0, V4)(V0, V5)(V0, V2)(V0, V2, V3)(V0, V4)(V0, V5)(V0, V2)(V0, V2, V3)(V0, V4)(V0, V5)(V0, V2)(V0, V4, V3)(V0, V4)(V0, V5)10503090(V0, V2)(V0, V4, V3)(V0, V4)(V0, V4, V5)10503090(V0, V2)(V0, V4, V3)(V0, V4)(V0, V4, V5)10503060(V0, V2)(V0,

8、 V4, V3)(V0, V4)(V0, V4, V3, V5)10503060(V0, V2)(V0, V4, V3)(V0, V4)(V0, V4, V3, V5)第9页/共20页第九页，共21页。辅助(fzh)结构 int D Dv:表示当前从源v0到顶点v的最短路径长度(chngd) int P Pvw为TRUE，则w是从v0到v当前求得最短路径上的顶点 Pv:表示从源v0到顶点v的最短路径上顶点v的所有前驱顶点 int final finalv为TRUE当且仅当vS，即已经求得v0到v的最短路径第10页/共20页第十页，共21页。Dijkstra算法(sun f) (1) 假设我们以

9、带权的邻接矩阵arcs表示有向网。 S：已求得最短路径的终点的集合。初始为空。 D初始化 Dvi=arcsv0vi vi V (2) 选择vj，使得D j=MinDi|vi V-S 令S=Svj (3) 修改从v出发到集合V-S上任意顶点(dngdin)vk可达的最短路径长度。 若 D j+arcs jk Dk, 则Dk=D j+arcs jk (4) 重复(2),(3)共n-1次。 由此求得从v到图上其余各顶点(dngdin)的最短路径是依路径长度递增的序列。第11页/共20页第十一页，共21页。 V0 V1 V2 V3 V4 V5 V0 10 30 100V1 5 V2 50 V3 10

10、V4 20 60 V5 V0,V2,V4,V3,V5 ,V1V0,V2,V4,V3,V5V0,V2,V4,V3V0,V2,V4V0,V2S=V0V1V5V3V4V2VjV5V4V3V26030501060V0,4,3,530501090V0,4,53050V0,4,310100V0,530V0,460V0,2,310100V0,530V0,410V0,2V1i=5i=4i=3i=2i=1 D 终点(zhngdin)V0V2V1V4V5V35503010101006020第12页/共20页第十二页，共21页。7.6 最短路径(ljng) 7.6.1 单源点最短路径 7.6.2 所有(suyu)顶

11、点对之间的最短路径第13页/共20页第十三页，共21页。问题描述： 已知一个各边权值均大于 0 的带权有向图，对每对顶点 vivj，要求求出每一对顶点之间的最短路径和最短路径长度。 解决方案： 1. 每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间(shjin)为O(n3)。 2. 形式更直接的弗洛伊德（Floyd）算法。时间(shjin)复杂度也为O(n3)。第14页/共20页第十四页，共21页。弗洛伊德算法(sun f)思想 欲求Vi到Vj的最短路径，依次求得中间顶点序号不大于k（k=0,1,.n-1）的最短路径。 具体过程P190.第

12、15页/共20页第十五页，共21页。定义定义(dngy)一个一个n阶方阵序列阶方阵序列D(-1),D(0),D(1),D(2),D(k),D(n-1)其中：其中： D(-1)ij= arcsij D(k)ij=Min D(k-1)ij, D(k-1)ik+ D(k-1)kj 0kn-1可见，可见，D(1)ij就是从就是从vi到到vj的中间顶点的序号不大于的中间顶点的序号不大于1的的 最短路径的长度最短路径的长度; D(k)ij就是从就是从vi到到vj的中间顶点的序号不大于的中间顶点的序号不大于k的的 最短路径的长度最短路径的长度; D(n-1)ij就是从就是从vi到到vj的最短路径的长度。的最

13、短路径的长度。0 4 116 0 23 0第16页/共20页第十六页，共21页。21CABCABCBCAABCABCABCABCBAABCABCABCABCBAACAB0210210210210P(2)P(1)P(0)P(-1)P2107320564007320664007320611400 320611400210210210210D(2)D(1)D(0)D(-1)DCABCBAACAB0 4 116 0 23 0第17页/共20页第十七页，共21页。本章(bn zhn)小结 1.熟悉图的各种存储结构及构造算法(特别是邻接矩阵和邻接表)，了解实际问题的求解效率与采用何种存储结构和算法有密切联

14、系。 2.熟练掌握(zhngw)图的两种搜索路径的遍历及算法。 3.掌握(zhngw)以下内容： 图的最小生成树和求最小生成树算法的思想; AOV网络的拓扑排序问题； AOE网络的关键路径法； 带权有向图的最短路径问题。第18页/共20页第十八页，共21页。作业(zuy) 7.11 实验 校园导游咨询 准备：设计分校的校园平面图，所含景点不少于10个。以顶点表示校内各景点，存放景点名称、代号、简介信息(xnx)；以边表示路径，存放路径长度信息(xnx)。 实验要求： 求得各景点之间的最短路径 语言不限 java、 vc6、vc9、 jsp+servlet、DotNet都可 图形界面（选作）第19页/共20页第十九页，共21页。感谢您的欣赏(xnshng)！第20页/共20页第二十页，共21页。NoImage内容