第2讲 最短路.ppt_第1页
第2讲 最短路.ppt_第2页
第2讲 最短路.ppt_第3页
第2讲 最短路.ppt_第4页
第2讲 最短路.ppt_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

最短路问题 双标号解法 标号 i j 的含义 第一标号i表示从始点到当前顶点的最短路线长度为i 第二标号j表示在从始点到当前顶点的最短路线上 当前顶点的前继顶点编号为j 最短路问题例 有向图 v1 v3 v2 v5 v6 v4 250 400 150 100 0 250 1 275 100 200 150 300 350 2 500 3 600 4 700 4 Dijstra最短路问题解法 在施行过程中 对于每个顶点Vj都要赋予一个标号 这分为固定标号 P标号 和临时标号 T标号 两类 含义如下 P标号 从起点到当前顶点的最短路长 T标号 从起点到当前顶点的最短路线长度的上界 注 每个顶点的标号只能够是P和T二者之一 如果为T标号 则有待修改 而一旦成为P标号 则固定不变了 具体标号过程 开始先给起点V1标上P标号0 给其余顶点标上T标号 然后检查与V1相邻的一切顶点Vj 选取到起点距离最小者 将其顶点T标号修改为P标号 以后每次检查刚得到P标号的顶点 检查与它相邻的一切顶点 同样从中选取到起点距离最小者 将其顶点T标号修改为P标号 由于每次都将一个T标号修改为P标号 总共n个顶点 故最多需要n 1次就可以将终点改为P标号 特别提示 Dijstra最短路解法对于具有负权的网络有可能失效 这种解法也可以采用图上标注的双标号方式 每一顶点的第一标号表明它的前继顶点 第二标号表明从起点到当前顶点的最短路线长度 标号过程正是将T标号顶点逐步修改为P标号顶点的过程 求最短路例 图上标注法 v1 v3 v2 v5 v6 v4 5 2 2 7 0 v1 5 1 3 6 7 v1 2 v2 7 v6 7 v3 6 v7 4 6 2 v5 10 最短路模型的应用 渡河问题 摆渡人需要将狼 羊和卷心菜带过河去 由于船小 每次只能够载一样东西 狼和羊 羊和卷心菜不能够在无人监视的情况下放在一起 您将如何安排渡河 平均分酒问题 有一只8升酒壶装满酒 另外有二只空酒壶分别为5升和3升 将酒平分的最简单方法是什么 思考 应该如何建立最短路模型求解 设备更新问题 某企业第一年年初花费11万元购买了一台新设备 问在5年内如何指定设备更新计划 使花费的总费用最少 假定设备各年年初的购买价格以及使用不同年限的维修费如下 作业 复习 图的基本概念 思考第一章习题1 2 1 10预习 第二章树作业本 习题1 4 习题1 29 习题1 30 补充题补充题 某设备今后5年内的价格分别为5 5 6 7 8 单位 万元 如果连续使用 其第n年的维修费分别为1 2 3 5 6 单位
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论