离散数学-图论课件打包第7章+图论-4（最短路问题）.ppt

第七章 图论 引言 7.1 图的基本概念 7.2 路与连通 7.3 图的矩阵表示 7.4 最短路径问题 7.5 图的匹配 8.1 Euler图和Hamilton图 8.2 树 8.3 生成树 8.4 平面图 7.4 最短路问题 一、问题的提出 7.4 最短路问题 路径 路径长度 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和 7.4 最短路问题 最短路问题在实际工作中应用 7.4 最短路问题 例 7.4 最短路问题 Dijkstra算法 Floyd算法 Floyd-Warshall算法 7.4 最短路问题 Dijkstra算法 7.4 .1 Dijkstra算法 Dijkstra算法基本思想:把图中所有结点分为两组，每一个结点对应一个距离值。 第一组：包括已确定最短路径的结点，结点对应的距离值是由v0到此结点的最短路径长度； 第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至此结点的最短路径长度。 按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。 7.4 .1 Dijkstra算法 7.4 .1 Dijkstra算法 procedure Dijkstra(G:所有权都为正数的加权连通简单图) {G带有顶点a＝v0,v1,…,vn＝z和权ω(vi,vj)，若(vi,vj)不是G的边，则ω(vi,vj)＝∞} for i:＝1 to n L(vi)＝∞ L(a):＝0 S:＝ （初始化标记，a的标记为0，其余结点标记为∞，S是空集} while z S begin u:＝不属于S的L(u)最小的一个顶点 S:＝S∪{u} for 所有不属于S的顶点v if L(u)＋ω(u,v)＜L(v) then L(v):＝L(u)＋ω(u,v) {这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记} end{L(z)＝从a到z的最短长度} 7.4 .1 Dijkstra算法 7.4 .1 Dijkstra算法 7.4 .1 Dijkstra算法 7.4 .1 Dijkstra算法 7.4 .1 Dijkstra算法 Dijkstra算法(另外一种说明) 7.4 .1 Dijkstra算法 0. 初始化：u1(1) ? 0，uj(1) ? d1j ( j =2,3,…,n) S(1) ? {v1}，S?(1) ? {v2 , v3 , … , vn}，m=1; 1. 选固定标号：在S?(m)中求vk，使得 uk(m) =min{uj(m) | vj?S?(m)}。 若 uk(m) =?，则S?(m)中的结点无最短路径；否则转2。 2. 判结束：令 S(m+1) ? S(m) ?{vk}, S?(m+1) ? S?(m) ?{vk} 若 m = n?1，结束。 3. 修改临时标号：对所有vj?S?(m+1) ，令 uj(m+1) =min{uj(m) , uk(m)+dkj}，m ?m+1；转1。 7.4 .1 Dijkstra算法 Dijkstra算法只求出图中一个特定的顶点到其他各定点的最短路。但在许多实际问题中，需求出任意两点之间的最短路，如全国各城市之间最短的航线，选址问题等。当然，要求出一个图的任意两点间的最短距路，只需将图中每一个顶点依次视为始点，然后用Dijkstra算法就可以了。 Dijkstra算法在物流配送中的应用 OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。 7.4 .1 Dijkstra算法 Floyd算法 如果有一个矩阵D=[d(ij)]，其中d(ij) 0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。通过这个距离矩阵D，把任意两个城市之间的最短路径找出来。 【分析】 对于任何一个城市而言，i 到 j 的最短距离不外乎存在经过 i 与 j 之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，检查d(ij)与d(ik)+d(kj)的值；d(ik)与d(kj)分别是目前为止所知道的 i 到 k 与 k 到 j 的最短距离，因此d(ik)+d(kj)就是 i