数 学 建 模 任意两个城市之间的最廉价路线 参与人员信息 ： 2012 年 6 月 6 日 一 、 问题提出 某 公 司 在 六 个 城 市 C1、 C2、 C3、 C4、 C5、 C6 中 都 有 分 公 司 ， 从 Ci 到 Cj 的直 达 航 班 票 价 由 下 述 矩 阵 的 第 i 行 、 第 j 列 元 素 给 出 （ ∞ 表 示 无 直 达 航 班 ）， 该公 司 想 算 出 一 张 任 意 两 个 城 市 之 间 最 廉 价 路 线 表 ， 试 做 出 这 样 的 表 来 。 0 50 ∞ 40 25 10 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 55 10 25 ∞ 25 55 0 二 、问题分析 若 网 络 中 的 每 条 边 都 有 一 个 数 值 (长 度 、 成 本 、 时 间 等 )， 则 找 出 两 节 点 (通常 是 源 节 点 和 阱 节 点 )之 间 总 权 和 最 小 的 路 径 就 是 最 短 路 问 题 。 最 短 路 问 题 是 网络 理 论 解 决 的 典 型 问 题 之 一 ， 可 用 来 解 决 管 路 铺 设 、 线 路 安 装 、 厂 区 布 局 和 设 备更 新 等 实 际 问 题 。 最 短 路 问 题 ， 我 们 通 常 归 属 为 三 类 ： 单 源 最 短 路 径 问 题 、 确 定起 点 终 点 的 最 短 路 径 问 题 、 全局 最 短 路 径 问 题 ———求图中 所有 的 最 短 路 径 。 题 中 要求算 出 一 张 任 意 城 市 间 的 最 廉 价 路 线 表 ， 属 于全局 最 短 路 问 题 ， 并且使得该 公 司 总 经理 能够与各个 子公 司 之 间 自由 往返。 （ 此两 点 为 主要约束条 件） Flo y d 算 法， 具体原理 如下 ： （ 1） 我 们 确 定 本 题 为 全局 最 短 路 问 题 ， 并采用 求距离 矩 阵 的 方 法 根 据 路 线 及 票 价 表 建 立 带 权 矩 阵W ， 并把 带 权 邻 接 矩 阵 我 w 作 为 距离 矩 阵的 初 始 值 ， 即(0)(0)()ijv vDdW （ 2） 求路 径 矩 阵 的 方 法 在 建 立 距离 矩 阵 的 同 时 可 建 立 路 径 矩 阵R ，( )ijv vRr，ijr 的 含 义 是 从iv 到jv的 最 短 路 ...
