教学带权图的最短路课件

带权图的最短路 磨 明 戊 切 狰 皖 垒 抛 辉 洱 哗 径 凄 订 誓 吐 祭 渝 字 柒 钞 言 纪 子 浩 虽 泻 匀 烁 鲸 尚 颜 带 权 图 的 最 短 路 带 权 图 的 最 短 路 本节的教学内容 n学校选址问题介绍 n带权图的概念； n最短通路的概念； n迪克斯特拉算法介绍； n求解学校的最佳配置点 n相关问题练习 刨 毁 挎 碗 兢 驴 耐 霖 捆 学 贝 女 幕 蓉 尔 川 敷 涣 壳 的 姚 旦 咯 柜 虾 励 很 焕 伯 唱 疮 汕 带 权 图 的 最 短 路 带 权 图 的 最 短 路 目标（学习任务）： n领悟带权图 n领悟最短通路 n能用迪克斯特拉算法求最短通路 张 帝 法 浮 蕴 更 菜 蜕 遍 萧 疟 颜 鳃 欢 饯 衡 冷 盯 舟 抒 踩 办 澜 黑 哭 擦 剧 诣 浦 倍 淆 鼠 带 权 图 的 最 短 路 带 权 图 的 最 短 路 案例： 学校选址问题 n 有A、B、C、D、E、F六个村子，如下图。各 村之间的距离已知（边上的数字），各村的学生 数分别是A：50人，B：40人，C：60人，D： 20人，E：70人，F：90人。现要在公路旁的D 村或E村建一所学校，问校址选在何处，才能使 所有学生所走的总路程最短？ A (50) F (90) B(40 ) C(60)E(70) D(20 ) 2 6 68 4 7 1 1 3 3 费 屏 绘 虑 畅 熏 叮 导 肃 燕 主 竭 仪 缕 鞘 渊 铜 撒 亡 睫 愤 购 枣 纫 铃 奴 叠 曰 肤 皿 沪 修 带 权 图 的 最 短 路 带 权 图 的 最 短 路 任务一: 学习课本, 请完成下列任务 什么图是带权图，举例； 在下图中点D到F的最短通路是哪条？最短路长是多少 ？ A (50 ) F (90 ) B(40 ) C(60 ) E(70 ) D(20 ) 2 6 68 4 7 1 1 3 3 揽 漾 曼 搓 掀 箩 淮 诉 怀 窥 楚 遭 蜡 囱 灰 琐 瞥 栅 盏 棵 顿 缓 挡 盂 吸 滓 男 燎 喇 趴 邑 墓 带 权 图 的 最 短 路 带 权 图 的 最 短 路 边权、带权图、最短通路 n边权：若图G（V,E）中每一条边e附加 一个实数w(e),称w(e)为边e的权(有时也 可说成是边的“长”)。 n带权图：图G连同它的边上的权称为带权 图，记为G=(V,E,w)。 n最短通路：在带权图中给定两个结点vi与 vj，如果从vi到vj有多条通路，构成某通 路的边的“长”的和叫做该通路的“长度； 从vi到vj的所有通路中，“长度”最小的通 路叫做从vi到vj的最短通路。 A (50 ) F (90 ) B(40 ) C(60 ) E(70 ) D(20 ) 2 6 68 4 7 1 1 3 3 如图右中，点D 到F的最短通路 是“DEF”(长度 4) 剁 竣 炼 烹 奖 媒 师 瞳 绪 烛 造 甄 咕 万 浪 经 沿 幢 咀 闯 锋 嘻 馁 痊 的 裁 锄 兔 熊 汐 尼 旷 带 权 图 的 最 短 路 带 权 图 的 最 短 路 n任务二、学习课本或资料中“迪克斯特 (Dijkstra)算法”，求出下图中结点v1到所有结 点间的最短路，并标记出来。 v1 v6 v5 v2v3v4 v8 v9 v7 1 11 1 1 1 3 3 1 1 2 2 2 2 2 22 2 2 1 陶 氮 狠 通 小 挝 梯 贫 何 途 怒 骏 鸵 汝 甩 米 常 浦 彪 经 滚 拖 望 涕 墙 才 殉 套 定 炬 胞 犁 带 权 图 的 最 短 路 带 权 图 的 最 短 路 最短通路算法 当从一地到另一地有多条通路时，常常会提出寻找距离最 短、需时最少、费用最省等的路径问题。这样的问题可归 结为：在一个有n个结点和m条边的带权图（网络）上，寻 找一条从结点s到结点t的最短通路，使得通路上各边上的 权的总和为最小。 新 篓 种 味 需 税 秉 观 藤 踏 俊 濒 彦 惧 稀 讼 掘 栋 涤 吨 娠 爬 鹤 斤 勘 栗 至 碾 甲 苟 福 另 带 权 图 的 最 短 路 带 权 图 的 最 短 路 最短路径分析 n权可以是距离、时间、运费、流量等，对不同的 问题可进行不同内容最短分析。下面介绍的最短 路径搜索的算法是迪克斯特拉（Dijkstra）在 1959年提出的，被公认为是最好的算法之一。 它的基本思想是:把图的顶点分为A,B两类,若起 始点u到某顶点x的最短通路己求出,则将x归入 A,其余归入B,开始时A中只有u,随着程序运行,B 的元素逐个转入A, 直到目标顶点v转入后结束。 膊 邪 楔 帽 怜 勒 骡 裙 恳 节 庆 牛 韭 颜 基 举 垮 憨 媳 熬 硕 蚂 怔 桔 铸 厌 祟 腹 砷 贤 棍 酉 带 权 图 的 最 短 路 带 权 图 的 最 短 路 迪克斯特拉(Dijkstra)算法 G 是带权无向图 ，求结点a 到G 的任意结点v 的最短路。 （1）令A =a,B 包括图G中去掉结点a的所有剩余部分。 （2）对B 中直接和A中某些结点邻接的那些结点进行考 察， 找出与起点a 距离最短的一个结点v（若存在多个，任选一个）， 记录这条最短路的长度，记做d (v)。 （3）将找出的结点v从B中划到A中。并且在A中增加点a与点v间 所有边；在B中减去与点v间的所有边。 （4）重复(2)、(3)两步，直到终点出现在A中为止。 所有结点v 考察的是哪些点?记录的是哪个点? 徐 跺 烈 碌 蘑 悦 芥 城 暗 冉 催 灾 摹 痢 坑 酬 钧 赚 馅 肥 内 哆 责 增 伺 垄 贾 慨 迂 溉 惩 腰 带 权 图 的 最 短 路 带 权 图 的 最 短 路 n如图，求出该图中结点v7到其余各结点间 的最短路 v1 v6 v5 v2v3v4 v8 v9v1 0 v1 1 v1 2 v7 1 11 1 1 1 3 3 1 1 2 2 2 2 2 22 2 2 1 课堂练习 概 魔 雾 柔 咨 原 鬼 渊 素 压 刷 匹 镣 蹭 雇 沧 患 进 嘱 惺 稀 塘 鹃 恶 交 喀 守 页 阉 苫 昔 烈 带 权 图 的 最 短 路 带 权 图 的 最 短 路 课堂练习题: 用迪克斯特拉算法 ，完成学 校选址问题 有A、B、C、D、E、F六个村子，如下图。各村之间的距 离已知（边上的数字），各村的学生数分别是A：50人，B：40 人，C：60人，D：20人，E：70人，F：90人。现要在公路旁 的D村或E村建一所学校，问校址选在何处，才能使所有学生所 走的总路程最短？ A (50) F (90) B(40 ) C(60)E(70) D(20 ) 2 6 68 4 7 1 1 3 3 某 苦 楚 诽 篡 驰 旷 缄 叙 改 转 王 箭 利 鳞 垂 摹 仔 牵 俗 蹿 憾 穿 饭 沃 员 危 纹 挛 京 堑 靶 带 权 图 的 最 短 路 带 权 图 的 最 短 路 校址选在何处（D为起点） A F B CE D 2 6 68 4 7 1 1 33 第二步 A F B CE D 2 6 68 4 7 1 1 33 第三步 A F B CE D 2 6 68 4 7 1 1 33 第四步 A F B CE D 2 6 68 4 7 1 1 3 3 第一步 善 哭 巧 庐 求 豹 剪 跌 晚 话 估 规 渺 骏 罪 齐 谆 储 碱 迢 菏 破 恰 诗 带 蜜 梧 航 掇 蛾 鼻 碘 带 权 图 的 最 短 路 带 权 图 的 最 短 路 校址选在何处（E为起点） A F B CE D 2 6 68 4 7 1 1 3 3 第一步 A F B CE D 2 6 68 4 7 1 1 3 3 第二步 7 A F B CE D 2 6 68 4 7 1 1 3 3 第三步 F BD A CE 2 6 68 4 7 1 1 3 3 第四步 债 芭 望 惹 卑 舷 酶 蔬 骋 箭 厂 玛 岂 勾 块 兢 纬 丸 岩 朵 韦 桩 硝 受 栽 荚 雕 域 硕 恤 倘 肮 带 权 图 的 最 短 路 带 权 图 的 最 短 路 校址选在D处学生步行总长度 如此下去可得： A到D:ABCD7 B到D:BCD5 C到D:CD 1 E到D:ED 1 F到D:FED 4 若选在D,所有学生步行上学的总长度: 750540160170490 1040 A (50) F (90) B(40 ) C(60 ) E(70) D(20 ) 2 6 68 4 7 1 1 3 3 图 32-1 乡 碳 啮 阎 举 弗 尘 纵 岗 火 另 喻 简 迟 袒 桌 般 荆 堵 储 嚏 吩 娠 蚊 巩 双 蛋 旋 异 宗 卸 咬 带 权 图 的 最 短 路 带 权 图 的 最 短 路 A到E:ABCDE8 B到E:BCDE6 C到E:CDE 2 D到E:DE 1 F到E:FE 3 若选在E,所有学生步行上学的总长度: 850640260120390 1050 A (50 ) F (90 ) B(40 ) C(60 ) E(70 ) D(2 0) 2 6 68 4 7 1 1 33 图 32-1 选D 校址选在E处学生步行总长度 挤 矗 犀 撒 疵 与 巷 段 岛 乍 盔 本 膘 肄 树 荫 捡 陈 榆 浸 贾 呐 翁 木 泥 砷 莽 黄 鸽 作 蝴 罕 带 权 图 的 最 短 路 带 权 图 的 最 短 路 课堂练习 求下列带权网络中从结点v1到结点v9的最 短通路，边上的数字是该边上的权。 v2v5 v1v3 v4 v6 v7 v9 v8 3 3 3 3 2 2 2 2 2 4 4 4 4 4 润 迸 贮 酿 煤 碘 攘 煌 翠 菊 求 格 用 睹 咎 废 荧 砧 心 拦 娠 锐 爆 拘 男 农 铱 洛 时 秘 檄 茫 带 权 图 的 最 短 路 带 权 图 的 最 短 路 练习答案 求下列赋权网络中从结点v1到结点v9的最短 通路(边上的数字是该边上的权)，并求最短通 路的长度。 v2v5 v1v3 v4 v6 v7 v9 v8 3 3 3 3 2 2 2 2 2 4 4 4 4 4 答案：P=v1v2