第7章 图论-4（最短路问题）.pptVIP

第七章 图论 引言 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