《第8讲 最短路问题实验.ppt》由会员分享，可在线阅读，更多相关《第8讲 最短路问题实验.ppt（28页珍藏版）》请在金锄头文库上搜索。
1、数学模型与数学实验 图论模型 实验目的 实验内容 2 会用Matlab软件求最短路 1 了解最短路的算法及其应用 1 图论的基本概念 2 最短路问题及其算法 3 最短路的应用 4 实验作业 固定起点的最短路 最短路是一条路径 且最短路的任一段也是最短路 假设在u0 v0的最短路中只取一条 则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此 可采用树生长的过程来求指定顶点到其余顶点的最短路 算法步骤 u1 u2 u3 u4 u5 u6 u7 u8 w function l z Dijkstra W n size W 1 fori 1 nl i W 1 i z i 1 endi 1 whil
2、ei nforj 1 n ifl i l j W j i l i l j W j i z i j ifj ii j 1 endendendi i 1 end floyd算法的基本思想 算法原理 求距离矩阵的方法 算法原理 求路径矩阵的方法 在建立距离矩阵的同时可建立路径矩阵R 即当vk被插入任何两点间的最短路径时 被记录在R k 中 依次求时求得 可由来查找任何点对之间最短路的路径 算法原理 查找最短路路径的方法 pk p2 p1 p3 q1 q2 qm 则由点i到j的最短路的路径为 算法步骤 a n size a 1 D a path zeros n n fori 1 nforj 1 nif
3、D i j infpath i j j j是i的后续点endendendfork 1 nfori 1 nforj 1 nifD i j D i k D k j D i j D i k D k j path i j path i k endendendendp sp mp sp fork 1 nifmp epd path mp ep p p d mp d endendd D sp ep path p 一 可化为最短路问题的多阶段决策问题 二 选址问题 1 中心问题 2 重心问题 例 企业要制定一台重要设备更新的五年计划 目标是使总费用 购置费用和维修费用之和 为最小 此设备在各年初价格及使用期中
4、所需维修数据如下 解 用点vi表示年初 i 1 2 6 v6表示第五年底 弧aij vi vj 表示第i年初购置设备使用到第j年初的过程 对应的权期间发生的购置费用和维修费用之和 原问题转变为从v1到v6的一条最短路 v1 v2 v3 v4 v5 v6 16 22 18 17 17 16 30 41 59 31 23 41 30 22 23 选址问题 中心问题 S v1 10 S v2 7 S v3 6 S v4 8 5 S v5 7 S v6 7 S v7 8 5 S v3 6 故应将消防站设在v3处 选址问题 重心问题 实验作业 可在下面两个题中任选其一 1 下表为某工程的全部工序以及工序时间与紧前工序 请完成以下问题 1 给出工程网络图 2 计算完成整个工程至少需要多少天 总工期 3 请问不误总工期的前提下 工程H可否延误 最多能够延误多少天 2 选址问题现准备在7个居民点中设置一银行 路线与距离如下图 问设在哪个点 可使最大服务距离最小 若设两个银行点呢
