Ｇ＝
３ 实例 分析
以 图 １ 示路 网结构 为例 ， 路 网用 邻接 矩 阵 所 该
Ｇ表示 ：
０ ４５ ∞ ∞ ∞ 。 。 ４ ０ ２３ ∞ 。 ３ ５ 。 ７ ∞ ２ ０ ３ ∞ ６ ∞ ５
∞ ∞ ｏ ０ ４ ∞ ｏ ３
若 顶点 ， 相邻 接
点间的多条路径简化为费率惟一的一条虚拟路径来
处理 。
Ｇｉ］ ｛ 若 点 不 接 ［ｊ＝∞ 顶 ， 邻 ， 【
０ ：
其中： 表示边上的权值。
则 图 １ 示路 ∞ ４ ０ ２ ∞ ∞ ３ ５ ３ ７
第 ２期
贺
鹏 等 ： 短路 径算 法浅 析 最
４ ３
径 法计 算联 网 收费 费 率 表 时 ， 需要 计 算 出任 意 两 个
匝道 出入 口之 间 的最 短路 径 ， 因此 ， 适合 使 用 更 Ｆ ｙｄ ｌ ｅ 算法。 ｏ Ｆ ｙｄ ｌ ｅ 算法使用图的邻接矩阵 Ａ进行 ｎ ｏ 次迭代 来计 算 每对顶 点 问 的最 短 路 径 ， 代 过 程 中得 到 一 迭 个 矩 阵序 列 Ａ ， … ， ， 阵 元 素 Ａ ［，］ 。Ａ ， 矩 “ ｉ 的值 即 Ｊ
（ ） 确认 路径 。在 产 生二 义性 路 径 的路 段 根 ２不
度优 先搜 索即可遍 历 图。 对于 有 ｎ个 顶点 的网络 ， 用 图论 ， 以用 × 利 可
ｎ的邻接矩 阵 Ｇ描述 ：
，
据 最 短路径 法 、 交通 分布法 、 车型分 类统计 法 或协 商
法等 算法确 定两 点 之 间 的唯 一 收 费费 率 ， 即把 起 止
行 费 的收取是 以车辆 在路 网 内的行驶 里程 为依据 进
行计 算 的 ， 因此 ， 二义 性路 径必然 给通行 费 的计算 带 来 困难 。根据 国内外 建设 经 验 ， 决 二义 性 路 径 问 解
题 的常用 方法 主要有 两类 。 （） １ 路径 确认 。通 过在 产 生二 义 性 路径 的路 段
物理结构 ， 讨论 用 Ｆｏｅ ｌｙｄ算法计算路 网中最短路径和路径长度 ， 给出了实现该算法的 Ｃ语 言程序 。 并 关键词 ： 高速公 路 ； 网收费 ； 联 最短路径 ；ｌ ｅ Ｆｏ ｄ算法 ｙ
中 图分 类号 ：４ ５ Ｕ９
随着 高速 公路路 网规模 的不 断扩 大 以及 联 网收 费 的实施 ， 必然 会 出现 二义 性 路径 问题 。所 谓 二 义 性路 径 ， 指从 高速 公 路 网某个 人 口至某 个 出 口之 是 间存 在 两条或 者多条 不 同的路径 。由于高 速公路 通
一
图 １ 高 速 公 路 网 络 结构 示 意
里程） 。实 施联 网收 费 的高速 公 路 网 络结 构必 然 为
个 连通 图 ， 即从 任 意顶 点 出 发进 行 深 度 优先 或广
上 设立 标识 站 ， 或者采 用车牌 识别 、Ｐ Ｇ Ｓ跟 踪定 位 等 技 术 手段来 精确 判断 车辆行 驶路 径 ；
上 述 两类方 法各 有优缺 点 。设 立标识 站等 技术 手 段虽 然 可 以精 确地 判 断车 辆行 驶 路 径 ， 系 统 的 但
建设、 维护、 管理等成本费用可能会远大于精确判断 车辆 行驶路 径 而带 来 的通 行 费 收 益 ， 时也 影 响 了 同 高速公路的通行效率。因此 ， 目前常见 的做法是根 据最短路径法来确定两点之间的唯一收费费率 ， 通 过协商法来解决通行费的拆分问题 。介绍了高速公 路 路 网结构 的数 学描 述方法 以及最 短路 径 的算 法 及
第２ ６卷
第 ２期
甘肃科 技
Ｇａ ｓ ｃ ｅ ｃ ｎ ｃ ｎ ｌｇ ｎ ｕ Ｓ ｉｎ ｅ ａ ｄ Ｔｅ ｈ ｏ ｏ ｙ
２６
． ２
２１ ００年 １ 月
Ｊｎ ａ ． ２ １ ００
最 短路 径 算 法浅 析
贺
摘
鹏 殷亚君 ，
（． １甘肃紫光智能交通与控制技术有限公司 ， 甘肃 兰州 ７ ０ １ ；． ３ ０ ０２ 甘肃省 高等级公路运营管理中心 ， 甘肃 兰州 ７ ００ ） ３００ 要： 高速公 路网结构 的数学模 型是高速公 路收 费和清分 的计算基 础。介 绍了用邻 接矩 阵来描 述高速公路 网的
２ 最短路径算 法及实现
目前已有众多成熟 的最短路径 算法 ， ， ｉ ・ 如 Ｄｊ ｋ
ｓａ ｔ 算法 ， ｒ 可以方便 的计算某一顶点到其余各顶点 的最短 路径 。另一 个典 型 算法 是 Ｆｏｅ 法 ， 以 ｌｙｄ算 可 计 算 图中每对顶 点之 间 的最 短路 径 。在使用 最短路
ｌ 高速公路路网结构 的数 学模型
高速公路网的物理结构可以用无 向带权 图（ 网 络） 来描述 ， 如图 １ 所示。
在 图 １中顶点 、 、 、 表 示高 速公 路 匝道 … 出人 口 ， 点 之间 的边 表 示 匝道 出人 口之 间 的连 接 两 关 系， 边上 的权 值表 示两点 之 间的距离 （ 际行驶 实
实现。
∞ ２ ０ ３ Ｇ＝ ∞ ∞ ∞
∞ ６ ∞ ５ ０ ４３ ∞
∞ ∞ ６ ４ ０ ８ ５ ３ ０ ∞ ３ ∞ ７ 。 ８ Ｏ ｏ Ｏ
显然 ， 矩阵 Ｇ为对称矩阵。在用计算机存储或 计算时可以用某个最大的权值或计算机可处理的最 大数来代替∞。
为从 顶点 ｉ 顶点 ＿ 到 『 的最 短路 径 。首 先 在路 径 （，） ｉ Ｊ 中插入 顶 点 ０ 考 虑 路 径 （ ， Ｊ ， 该 路 径 存 在 ， ， ｉ０， 若 ） 比 较 路径 （√ 和路 径 （，， 的长度 ， 长度 较 短者 作 ｉ） ｉＯ ） 取 为 从顶 点 ｉ 到顶 点 且 中 间顶 点 编 号 不 大 于 ０的最