图论-4(最短路问题).ppt

第七章图论 引言7 1图的基本概念7 2路与连通7 3图的矩阵表示7 4最短路径问题7 5图的匹配8 1Euler图和Hamilton图8 2树8 3生成树8 4平面图 7 4最短路问题 一 问题的提出 赋权图 网络 G V E 中 给每条边a 赋予一个非负实数权wij 得到一个有向网络 7 4最短路问题 路径路径长度非带权图的路径长度是指此路径上边的条数 带权图的路径长度是指路径上各边的权之和 距离矩阵 对上述网络 定义D dij n n n V wij当 Edij 其它 带权路径长度 对上述网络 路径v1 v2 vk的带权路径长度定义为 7 4最短路问题 最短路问题在实际工作中应用 1 通讯网络中最可靠问题2 最大容量问题3 统筹方法中求关键路线4 背包问题5 选址问题6 工件加工顺序问题7 中国邮递员问题 背包问题 Knapsackproblem 是一种组合优化的NP完全问题 问题可以描述为 给定一组物品 每种物品都有自己的重量和价格 在限定的总重量内 我们如何选择 才能使得物品的总价格最高 问题的名称来源于如何选择最合适的物品放置于给定背包中 7 4最短路问题 例 一位旅客要从A城到B城他希望选择一条途中中转次数最少的路线 他希望选择一条途中所花时间最短的路线 他希望选择一条途中费用最小的路线 这些问题均是带权图上的最短路径问题 边上的权表示一站边上的权代表距离边的权代表费用 7 4最短路问题 Dijkstra算法Floyd算法Floyd Warshall算法 7 4最短路问题 Dijkstra算法 Dijkstra算法是由荷兰计算机科学家狄克斯特拉 Dijkstra 于1959年提出的 因此又叫狄克斯特拉算法 是从一个顶点到其余各顶点的最短路径算法 解决的是有向图中最短路径问题 荷兰计算机科学教授EdsgerW Dijkstra 1930 在1972年获得美国计算机协会授予的图灵奖 这是计算机科学中最具声望的奖项之一 Dijkstra算法是求出一个连通加权简单图中从结点a到结点z的最短路 边 i j 的权 i j 0 且结点x的标号为L x 结束时 L z 是从a到z的最短长度 举例来说 如果图中的顶点表示城市 而边上的权重表示城市间开车行经的距离 Dijkstra算法可以用来找到两个城市之间的最短路径 7 4 1Dijkstra算法 Dijkstra算法基本思想 把图中所有结点分为两组 每一个结点对应一个距离值 第一组 包括已确定最短路径的结点 结点对应的距离值是由v0到此结点的最短路径长度 第二组 包括尚未确定最短路径的结点 结点对应的距离值是v0经由第一组结点 中间结点 至此结点的最短路径长度 按最短路径长度递增的顺序把第二组的结点加到第一组中去 直至v0可达的所有结点都包含于第一组 在这个过程中 总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度 7 4 1Dijkstra算法 设源点为v0初始时v0进入第一组 v0的距离值为0 第二组包含其它所有结点 这些结点对应的距离值这样确定 设vi为第二组中的结点 然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中 每往第一组加入一个结点vm 就要对第二组的各结点的距离值作一次修正 设vi为第二组的结点 若加进vm做中间结点使得v0至vi的路径长度更短 即vi的距离值 vm的距离值 Wmi 则要修改vi的距离 vi的距离值 vm的距离值 Wmi 修改后再选距离值最小的一个结点加入到第一组中 如此进行下去 直至第一组囊括图的所有结点或再无可加入第一组的结点存在 显然 这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略 7 4 1Dijkstra算法 procedureDijkstra G 所有权都为正数的加权连通简单图 G带有顶点a v0 v1 vn z和权 vi vj 若 vi vj 不是G的边 则 vi vj fori 1tonL vi L a 0S 初始化标记 a的标记为0 其余结点标记为 S是空集 whilezSbeginu 不属于S的L u 最小的一个顶点S S u for所有不属于S的顶点vifL u u v L v thenL v L u u v 这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记 end L z 从a到z的最短长度 dij 7 4 1Dijkstra算法 下面给出该算法的框图 通过框图 容易计算该算法计算量 7 4 1Dijkstra算法 下面通过一个实例来说明Dijkstra算法是如何工作的 7 4 1Dijkstra算法 7 4 1Dijkstra算法 1 用Dijkstra算法求a和z之间最短路所用的步骤 7 4 1Dijkstra算法 Dijkstra算法 另外一种说明 求有向网络G V A 中结点v1到其它结点的最短距离 设D为G的距离矩阵 n V 向量U u1 u2 un 的ui标记结点v1到vi的距离 S为已取得最短路的结点集合 其中每个结点在U中有固定标号标记取得的最短路的长度 S 为未取得最短路的结点集合 其中每个结点在U中有临时标号 7 4 1Dijkstra算法 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 1Dijkstra算法 Dijkstra算法只求出图中一个特定的顶点到其他各定点的最短路 但在许多实际问题中 需求出任意两点之间的最短路 如全国各城市之间最短的航线 选址问题等 当然 要求出一个图的任意两点间的最短距路 只需将图中每一个顶点依次视为始点 然后用Dijkstra算法就可以了 Dijkstra算法在物流配送中的应用OSPF openshortestpathfirst 开放最短路径优先 算法是Dijkstra算法在网络路由中的一个具体实现 7 4 1Dijkstra算法 Dijkstra算法要求图上的权是非负数 否则结果不正确 Dijkstra算法同样适用于无向图 此时一个无向边次相当于两个有向边 利用求最短路的方法求最长路 由于存在负权 求最长路和负权等价 所以在这里Dijkstra算法不适用了 必须采用Floyd算法 动态规划算法Floyd算法的功能是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵 7 4 2Floyd算法 如果有一个矩阵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到j经过k的最短距离 所以 若有d ij d ik d kj 就表示从i出发经过k再到j的距离要比原来的i到j距离短 自然把i到j的d ij 重写为d ik d kj 每当一个k查完了 d ij 就是目前的i到j的最短距离 重复这一过程 最后当查完所有的k时 d ij 里面存放的就是i到j之间的最短距离了 7 4 2Floyd算法 定义7 4 1 已知矩阵A aij m l B bjk l n 规定C A B cij m n 其中cij min ai1 b1j ai2 b2j ail blj 定义7 4 2已知矩阵A aij m n B bij m n 规定D AB dij m n 其中dij min aij bij 可以利用上面定义的运算求任意两点间的最短距离 已知n阶加权简单图G 设D dij m n是图G的边权矩阵 即dij i j 若G是有向图 则dij 若结点i到结点j无边相连时 则取dij 然后依次计算出矩阵D 2 D 3 D n 及S 7 4 2Floyd算法 其中D 2 D D n nd 2 ij min di1 d1j di2 d2j din dnj d 2 ij表示从vi出发两步可以到达vi的道路中距离最短者 D 3 D 2 D n n d k ij表示从vi出发k步可以到达vj的道路中距离最短者D n D n 1 D n nS DD 2 D 3 D n Sij n n由定义可知dij k 表示从结点i到j经k边的路 在有向图中即为有向路 中的长度最短者 而Sij为结点i到j的所有路 若是有向图即为有向路 中的长度最短者 Floyd算法的时间复杂性是O n4 7 4 2Floyd算法 求下图各点间的最短路径 7 4 2Floyd算法 解 D 2 12 13 7 12 3 6 12 13 7 12 3 6 2348 236 4 7 4 2Floyd算法 类似可得 346 5 D 3 D 5 D 4 6 7 4 2Floyd算法 所以 S DD 2 D 3 D 4 D 5 sij 6 6 7 4 3Floyd Warshall算法 Floyd Warshall算法是解决任意两点间的最短路径的一种算法 基本思想 通过求解矩阵序列D 0 D 1 D n 来实现问题的求解 7 4 3Floyd Warshall算法 其中 D 0 图的距离矩阵 D n 最终解 dij 边 vi vj 的权值d k ij 从vi到vj在所经过的顶点号 k最短路径长度 即通过依次比较顶点修改路径实现求解的 对于任意两个顶点vi vj 对于新比较的顶点vk一旦出现d k 1 ij dik dkj 则修改对应的d k ij 7 4 3Floyd Warshall算法 例 求下图各点间的最短路径 7 4 3Floyd Warshall算法 解 比较经过顶点号 1的矩阵 D 1 12 13 7 12 3 6 123456 123456 无改变 7 4 3Floyd Warshall算法 解 比较经过顶点号 2的矩阵 D 2 12 13 7 12 3 6 123456 123456 4 8 d 1 14 d12 d24所以修改d 2 14 d 1 16 d12 d26所以修改d 2 16 7 4 3Floyd Warshall算法 解 比较经过顶点号 3的矩阵 D 3 124 8 13 7 12 3 6 123456 123456 4 2 3 3 d 2 14 d13 d34 d 2 15 d13 d35 d 2 24 d23 d34 d 2 25 d23 d35 7 4 3Floyd Warshall算法 解 比较经过顶点号 4的矩阵 D 4 12248 1237 12 3 6 123456 123456 6 5 4 d 3 16 d13 d34 d46 d 3 26 d23 d34 d46 d 3 36 d34 d46 7 4 3Floyd Warshall算法 解 比较经过顶点号 5的矩阵 D 5 12346 1235 124 3 6 123456 123456 无改变 7 4 3Floyd Warshall算法 解 比较经过顶