《最短路算法讲述》由会员分享，可在线阅读，更多相关《最短路算法讲述（35页珍藏版）》请在金锄头文库上搜索。
1、最短路问题是网络理论中应用最广泛的问题之一。许多优 化问题都可以使用这个模型，如设备更新、管道的铺设、 线路的安排、厂区的布局等。 最短路问题的一般提法是：设 为连通图，图中 各边 有权 ( 表示 ， 之间没有边）, 为图中任意两点，求一条道路 ，使它是从 到 的所有路中总权最小的路。即： 最小。 3 最短路问题 最短路算法中1959年由 （狄克斯特洛）提出的 算法被公认为是目前最好的方法，我们称之为 算 法。下面通过例子来说明此法的基本思想。 条件：所有的权数 思路：逐步探寻。 下求 到 的最短路： 1）从 出发，向 走。首先，从 到 的距离为0，给 标号（0）。画第一个弧。（表明已 标号，
2、或已走出 ） 从 出发，只有两条路可走 ，其距离为2） 可能最短路为 给 划成粗线。 划第二个弧。 给 标号（4）。 表明走出 后走向 的最短路目前看是 ，最优距离 是4 。 现已考察完毕第二个圈内的路，或者说，已完成 的标号。 3）接着往下考察，有三条路可走： 可选择的最短路为 给 划成粗线。 划第3个弧。 给 标号（6）。 4）接着往下考察，有四条路可走： 可选择的最短路为 给 划成粗线。 划第4个弧。 给 标号（8）。 5）接着往下考察，有四条路可走： 可选择的最短路为 给 划成粗线。 划第5个弧。 给 标号（9）。 6）接着往下考察，有四条路可走： 可选择的最短路为 给 划成粗线。 划
3、第6个弧。 给 标号（13）。 7）接着往下考察，有四条路可走： 可选择的最短路为 同时给 划成粗线。 分别给 标号（14）。 最后，从 逆寻粗线到 ，得最短路： 长度为14。 最短路问题的两个应用 最短路问题在图论应用中处于很重要的地位，下 面举两个实际应用的例子。 若已知设备在各年的购买费，及不同机器役龄时的 残值与维修费，如表所示. 例1 设备更新问题 某工厂使用一台设备，每年年初工厂要作出决定：继 续使 用旧的还是购买新的？如果继续使用旧的，要 付维修费；若要购买 一套新的，要付购买费。试确 定一个5年计划，使总支出最小. 项项目第1年第2年第3年第4年第5年 购买费购买费111213
4、1414 机器役龄龄0-11-22-33-44-5 维维修费费5681118 残值值43210 解：把这个问题化为最短路问题。 用点 表示第i年初购进一台新设备，虚设一个点 ，表示第 5年底。 边 表示第i年购进的设备一直使用到第j年初（即第j-1 年底）。 边 上的数字表示第i年初购进设备，一直使用到第j年 初所需支付的购买费、维修的全部费用（可由表8-2计算得 到）。 这样设备更新问题就变为：求从 到 的最短路问题. 给 划成彩线。 给 划成彩线。 给 划成彩线。 给 划成彩线。 给 划成彩线。 计算结果：最短路 最短路路长为49。 即：在第一年、第三年初各购买一台新设备为最优决策。 这时
5、5年的总费用为49。 例2 (选址问题P) 已知某地区的交通网络如图8-37所示， 其中点代表居民小区，边代表公路，为小区间公路距离，问区 中心医院应建在哪个小区，可使离医院最远的小区居民就诊时 所走的路程最近？ 解 求中心的问题。 解决方法：先求出 到 其它各点的最短路长 如 再求 即为所求。 比如求 给 划线。 给 划线。 给 标号20。 给 划线。 给 标号30。 分别给 划线。 分别给 标号33。 给 划成彩线。 给 标号63。 其它计算结果见下表： 小区号 0 30 50 63 93 45 6093 30 0 20 33 63 15 3063 50 20 0 20 50 25 405
6、0 63 33 20 0 30 18 3363 93 63 50 30 0 48 6393 45 15 25 18 48 0 1548 60 30 40 33 63 15 063 由于 最小，所以医院应建在 ，此时离医院最 远的小区 距离为48。 Floyd （佛洛伊德）算法 这里介绍得Floyd（1962年）可直接求出网络中任意两 点间的最短路。 令网络中的权矩阵为 其中 当 其他 算法基本步骤为： 输入权矩阵 例 计算 其中 例如： 中不带角标的元素表示从 到 的距离（直接有边）， 带角标的元素表示借 为中间点时的最短路长。 中不带角标的元素表示从 到 的距离（直接有边）， 带角标的元素表示借 为中间点时的最短路长。 在放开 的基础上，再放开 注意到： 在放开 点的基础上，再放开 考察最短路。 注意到： 说明所有点经过 并没有缩短路程。 只有一个新增元素 表示任意两点间的最短路长及其路径。
