「运筹学-最短路问题[课件参考]」.ppt

运筹学 OperationsResearch 精选课件 Chapter8图与网络优化 8 1图的基本概念 8 2树 8 3最短路问题 8 4网络最大流问题 8 5最小费用最大流问题 8 6中国邮递员问题 本章主要内容 精选课件 8 3最短路问题 TheShortest PathProblem 精选课件 如何用最短的线路将三部电话连起来 此问题可抽象为设 ABC为等边三角形 连接三顶点的路线 称为网络 这种网络有许多个 其中最短路线者显然是二边之和 如AB AC A B C 8 3最短路问题 精选课件 A B C P 但若增加一个周转站 新点P 连接4点的新网络的最短路线为PA PB PC 最短新路径之长N比原来只连三点的最短路径要短 这样得到的网络不仅比原来节省材料 而且稳定性也更好 8 3最短路问题 精选课件 最短路问题 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 有些问题 如选址 管道铺设时的选线 设备更新 投资 某些整数规划和动态规划的问题 也可以归结为求最短路的问题 因此这类问题在生产实际中得到广泛应用 8 3最短路问题 8 3 1最短路问题 精选课件 定义设连通图D V A 每一弧a vi vj 有一个非负权w a wij wij 0 如果P是D中从vs到vt的一条路 称P中所有弧的权之和为路P的权 记为w P 8 3最短路问题 定义设D为有向赋权图 vs与vt是D中两点 在连接vs与vt的所有路中 权最小的路P0称为从vs到vt的最短路 即 最小的路P0的权称为从vs到vt的距离 记为 权值的意义是广泛的 可以表示距离 可以表示交通运费 可以表示网络流量 在朋友关系图甚至可以表示友谊深度 但都可以抽象为距离 精选课件 8 3最短路问题 常见的最短路算法 1 Dijkstra算法 2 Floyd Warshall算法 Dijkstra算法是典型的单源最短路径算法 用于计算一个节点到其他所有节点的最短路径 主要特点是以起始点为中心向外层层扩展 直到扩展到终点为止 Dijkstra算法在很多专业课程如数据结构 图论 运筹学等中都作为基本内容有详细的介绍 Floyd Warshall算法是解决任意两点间的最短路径的一种算法 可以正确处理有向图或负权的最短路径问题 注意该算法要求不存在负权边 精选课件 迪杰斯特拉 1930 2002 荷兰人 早年钻研物理及数学 转为计算学 1972年获图灵奖 计算机界的诺贝尔奖 8 3最短路问题 1959年 Dijkstra发现了在赋权图中求最短路的算法 8 3 2狄克斯特拉算法 Dijkstraalgorithm 也称双标号法 1 提出 goto有害论 2 提出信号量和PV原语 3 解决了 哲学家聚餐 问题 4 最短路径算法和银行家算法的创造者 5 第一个Algol60编译器的设计者和实现者 6 THE操作系统的设计者和开发者 与D E Knuth并称为这个时代最伟大的计算机科学家的人 精选课件 若P是从vs到vt间的最短路 vi是P中的一个点 则vs到vi的最短路就是从vs沿P到vi的那条路 v1 v2 v3一定是v1 v3的最短路 v2 v3 v4也一定是v2 v4的最短路 1 最短路算法基于以下原理 8 3最短路问题 一个最优策略的任一子策略也是最优策略 精选课件 从vs出发 给网络中的每个点对应记录一个数 称为这个点vi的标号 它或者表示从vs到该点vi的最短路的权 称为P标号 此为永久标号 或者是从vs到该点vi的最短路的权的上界 称为T标号 此为临时标号 方法的每一步是去修改T标号 并且把某一个具T标号的点改变为具P标号的点 从而使D中具P标号的顶点数多一个 这样至多经过p 1步 当终点vt得到 标号时 就可以求出从vs到各点的最短路 2 Dijkstra算法 8 3最短路问题 1 基本思想 精选课件 P v T v 分别表示点v的P标号和T标号 Si表示第i步时具P标号点的集合 为了在求出从vs到各点的距离的同时 也求出从vs到各点的最短路 给每个点v以一个 值 算法终止时 若 v m 表示在从vs到v的最短路上 v的前一个点是vm 若 v M 表示D中不含从vs到v的路 若 v 0表示v vs 8 3最短路问题 2 标号含义 精选课件 8 3最短路问题 s 1 d v1 v1 0 v1是具P标号的点 现考查从v1发出的三条弧 v1 v2 v1 v3 和 v1 v4 min d v1 v1 12 d v1 v1 w13 d v1 v1 w14 d v1 v1 w14 1 所以从v1出发到v4所需的最小费用必定是1单位 这样就可使v4变成具P标号的点 精选课件 令dij表示vi到vj的直接距离 两点之间有边 若两点之间没有边 则令dij 若两点之间是有向边 则dji 令dii 0 s表示始点 t表示终点 2 标号含义 精选课件 1 给始点vs以P标号 这表示从vs到vs的最短距离为0 其余节点均给T标号 2 设节点vi为刚得到P标号的点 考虑点vj 其中 且vj为T标号 对vj的T标号进行如下修改 3 比较与vi相邻的所有具有T标号的节点 把最小者改为P标号 即 当存在两个以上最小者时 可同时改为P标号 若全部节点均为P标号 则停止 否则用vk代替vi 返回步骤 2 8 3最短路问题 3 算法步骤 精选课件 8 3最短路问题 例8 8用Dijkstra算法求下图从v1到v8的最短路 精选课件 解 1 首先给v1以P标号 给其余所有点T标号 2 8 3最短路问题 精选课件 8 3最短路问题 3 精选课件 8 3最短路问题 4 精选课件 8 3最短路问题 5 精选课件 8 3最短路问题 6 精选课件 故算法终止 反向追踪得v1到v8最短路为 8 3最短路问题 7 精选课件 8 3最短路问题 3 v3 v8 v7 v2 v5 v6 v4 6 2 3 4 1 2 7 1 2 3 v1 2 0 3 5 6 6 10 8 9 精选课件 精选课件 8 3最短路问题 例8 6用Dijkstra算法求下图从v1到v6的最短路 精选课件 解 1 2 8 3最短路问题 精选课件 3 4 8 3最短路问题 精选课件 8 3最短路问题 5 6 精选课件 7 8 8 3最短路问题 精选课件 故算法终止 得反向追踪得v1到v8的最短路为 8 3最短路问题 9 精选课件 8 3最短路问题 如图 精选课件 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 8 3最短路问题 例8 9用Dijkstra算法求下图从1到8的最短路 精选课件 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 S 1 P1 0 min c12 c14 c16 min 0 2 0 1 0 3 min 2 1 3 1 p4 1 p1 0 8 3最短路问题 S 1 4 P4 1 精选课件 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 min c12 c16 c42 c47 min 0 2 0 3 1 10 1 2 min 2 3 11 3 2S 1 2 4 p2 2 p1 0 p4 1 p2 2 8 3最短路问题 精选课件 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 S 1 2 4 min c13 c23 c25 c47 min 0 3 2 6 2 5 1 2 min 3 8 7 3 3S 1 2 4 6 P6 3 p2 2 p4 1 p1 0 p6 3 8 3最短路问题 精选课件 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 S 1 2 4 6 min c23 c25 c47 c67 min 2 6 2 5 1 2 3 4 min 8 7 3 7 3S 1 2 4 6 7 P7 3 p2 2 p4 1 p1 0 p6 3 p7 3 8 3最短路问题 精选课件 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 S 1 2 4 6 7 min c23 c25 c75 c78 min 2 6 2 5 3 3 3 8 min 8 7 6 11 6S 1 2 4 5 6 7 P5 6 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 8 3最短路问题 精选课件 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 S 1 2 4 6 7 min c23 c53 c58 c78 min 2 6 6 9 6 4 3 8 min 8 15 10 11 8S 1 2 3 4 5 6 7 P3 8 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 8 3最短路问题 精选课件 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 S 1 2 3 4 6 7 min c38 c58 c78 min 8 6 6 4 3 7 min 14 10 11 10S 1 2 3 4 5 6 7 8 P8 10 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 p8 10 8 3最短路问题 精选课件 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 S 1 2 3 4 6 7 8 1到8的最短路径为 1 4 7 5 8 长度为10 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 p8 10 8 3最短路问题 精选课件 由此看到 此方法不仅求出了从v1到v8的最短路长 同时也求出了从v1到任意一点的最短路长 将从v1到任一点的最短路权标在图上 即可求出从v1到任一点的最短路线 本例中v1到v8的最短路线是 8 3最短路问题 v1 v2 v5 v6 v8 精选课件 从上例知 只要某点已标号 说明已找到起点vs到该点的最短路线及最短距离 因此可以将每个点标号 求出vs到任意点的最短路线 如果某个点vj不能标号 说明vs不可达vj 注 无向图最短路的求法只将上述步骤2将弧改成边即可 8 3最短路问题 精选课件 例8 7用Dijkstra算法求下图从v1到v6的最短路 解 1 首先给v1以P标号 给其余所有点T标号 2 3 4 8 3最短路问题 精选课件 5 6 7 8 9 10 反向追踪得v1到v6的最短路为 8 3最短路问题 精选课件 作业 P239习题8 10 8 3最短路问题 精选课件 小结 学习要点 1 理解最短路问题的概念 2 理解Dijkstra算法的思想3 掌握Dijkstra算法的步骤 Dijkstra算法 Prim算法和Kruskal算法都属于典型的贪心算法 精选课件 Theend thankyou 精选课件 最短路问题 例6 4渡河游戏一老汉带了一只狼 一只羊 一棵白菜想要从南岸过河到北岸 河上只有一条独木舟 每次除了人以外 只能带一样东西 另外 如果人不在 狼就要吃羊 羊就要吃白菜 问应该怎样安排渡河 才能做到既把所有东西都运过河去 并且在河上来回次数最少 这个问题就可以用求最短路方法解决 精选课件 最