最短路问题.ppt

最短路问题 一 固定起点的最短路二 任意两点的最短路三 最短路算法的应用 最短路问题 SPP shortestpathproblem 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地 从甲地到乙地的公路网纵横交错 因此有多种行车路线 这名司机应选择哪条线路呢 假设货柜车的运行速度是恒定的 那么这一问题相当于需要找到一条从甲地到乙地的最短路 一 固定起点的最短路 问题 无向连通简单带权图 求出顶点a与z之间的最短通路的长度 最短路问题是网络理论中应用最广的问题之一 许多优化问题可以使这个模型 如设备更新 管道铺设 线路安排 厂区布局等 图论方法比较有效 算法思想 最短路是一条路径 且最短路的任一段也是最短路 求出从a到第一个顶点的最短通路的长度 从a到第二个顶点的最短通路的长度 依次类推 直到求出从a到z的最短通路的长度为止 即类似于树生长的过程 算法步骤 TOMATLAB road1 u1 u2 u3 u4 u5 u6 u7 u8 2 1 8 1 5 2 9 3 9 7 6 3 4 1 6 第0步 u2 u3 u4 u5 u6 u7 u8 2 1 8 1 5 2 9 3 9 7 6 3 4 1 6 u1 第1步 u3 u2 u3 u4 u5 u6 u7 u8 2 1 8 1 5 2 9 3 9 7 6 3 4 1 6 2 u1 8 u1 1 u1 u1 第2步 u3 10 u1 u3 u2 u2 u3 u4 u5 u6 u7 u8 2 1 8 1 5 2 9 3 9 7 6 3 4 1 6 2 u1 8 u1 1 u1 u1 第3步 u3 10 u1 u3 u2 3 u1 u2 u5 u2 u3 u4 u5 u6 u7 u8 2 1 8 1 5 2 9 3 9 7 6 3 4 1 6 2 u1 8 u1 1 u1 u1 第4步 u3 10 u1 u3 u2 3 u1 u2 u6 6 u1 u2 u5 12 u1 u2 u5 u5 u2 u3 u4 u5 u6 u7 u8 2 1 8 1 5 2 9 3 9 7 6 3 4 1 6 2 u1 8 u1 1 u1 u1 第5步 u3 10 u1 u3 u2 3 u1 u2 u6 6 u1 u2 u5 12 u1 u2 u5 u5 7 u1 u2 u5 u6 u4 u2 u3 u4 u5 u6 u7 u8 2 1 8 1 5 2 9 3 9 7 6 3 4 1 6 2 u1 1 u1 u1 第6步 u3 10 u1 u3 u2 3 u1 u2 u6 6 u1 u2 u5 12 u1 u2 u5 u5 7 u1 u2 u5 u6 u4 9 u1 u2 u5 u6 u4 u7 u8 u3 u4 u6 u7 u1 u3 u2 u6 u5 u4 u7 u8 例2求出点1到其余各顶点的最短有向路的长度 Dijkstra算法 例3狼 羊 白菜问题 狼 羊 白菜过河问题猎人要把一只狼 一头羊和一篮白菜从河的左岸带到右岸 但他的渡船太小 一次只能带一样 因为狼要吃羊 羊会吃白菜 所以狼和羊 羊和白菜不能在无人监视的情况下相处 问猎人怎样才能达到目的 人 狼 羊 菜四种的任意组合共有16种 其中狼羊菜 狼羊 羊菜三种不允许出现 所以人 人狼 人菜也不允许出现 因此 允许出现的情况共有以下10种情况 人狼羊菜 人狼羊 人狼菜 人羊菜 人羊 狼菜 狼 菜 羊及空 把这10种状态视为10个点 若一种状态通过一次摆渡后可变为另一种状态 则在两种状态 点 之间画一直线 得示意图如下 将各顶点到 人狼羊菜 的距离标在图中各顶点处 可知有两种最迅速最安全的渡河方案 1 人狼羊菜 狼菜 人狼菜 狼 人狼羊 羊 人羊 空 2 人狼羊菜 狼菜 人狼菜 菜 人羊菜 羊 人羊 空 每种方案都要七次 这种 用顶点代表状态 边代表状态间的转移 的状态转移图模型颇具代表性 任何具有有限个状态的多步决策问题都可以类似地建立图的模型 利用图论工具来解决 这样摆渡问题就转化成在图中找出以 人狼羊菜 为起点 以 空 为终点的简单路 二 任意两点间的最短路问题 算法原理 求距离矩阵的方法 算法原理 求路径矩阵的方法 在建立距离矩阵的同时可建立路径矩阵R 算法原理 查找最短路路径的方法 pk p2 p1 p3 q1 q2 qm 则由点i到j的最短路的路径为 算法步骤 第0步 12 12 1 1 第2步 11 11 16 16 19 19 2 2 2 2 2 2 第3步 第4步 TOMATLAB road2 floyd 建模实例 最优截断切割问题1997B 奥运会临时超市网点设计2004B 例1某工厂使用一种设备 这种设备在一定的年限内随着时间的推移逐渐损坏 所以工厂在每年年初都要决定设备是否更新 若购置设备 每年需支付购置费用 若继续使用旧设备 需要支付维修与运行费用 而且随着设备的老化会逐年增加 计划期 五年 内中每年的购置费 维修费与运行费如表所示 工厂要制定今后五年设备更新计划 问采用何种方案才能使包括购置费 维修费与运行费在内的总费用最小 三 最短路应用 28 v1 v2 v3 v4 v5 v6 23 25 26 29 30 42 60 85 32 44 62 33 45 35