最 短 路 径 算 法 及 应 用 乘 汽 车 旅 行 的 人 总 希 望 找 出 到 目 的 地 的 尽 可 能 的 短 的 行 程
如 果 有 一 张 地 图 并 在 图 上 标出 每 对 十 字 路 口 之 间 的 距 离 ， 如 何 找 出 这 一 最 短 行 程
一 种 可 能 的 方 法 就 是 枚 举 出 所 有 路 径 ，并 计 算 出 每 条 路 径 的 长 度 ，然 后 选 择 最 短 的 一 条
那 么 我 们 很 容 易 看 到 ， 即 使 不 考 虑 包 含 回 路 的 路 径 ， 依 然 存 在 数 以 百 万 计 的 行 车 路 线 ， 而 其中 绝 大 多 数 是 不 值 得 考 虑 的
在 这 一 章 中 ， 我 们 将 阐 明 如 何 有 效 地 解 决 这 类 问 题
在 最 短 路 径 问 题 中 ， 给 出 的 是 一 有向 加 权 图 G＝ （ V， E， W） ， 其 中 V 为 顶 点 集 ， E为 有 向 边 集 ， W 为 边 上 的 权 集
最 短 路 径 问题 研 究 的 问 题 主 要 有 ： 单 源 最 短 路 径 问 题 、 与所 有 顶 点 对 之 间 的 最 短 路 径 问 题
一 、 单 源 最 短 路 径 问 题 所 谓单 源 最 短 路 径 问 题 是 指： 已知图 G＝ （ V， E） ， 我 们 希 望 找 出 从某给 定的 源 结点 S∈V到 V 中 的 每 个结点 的 最 短 路 径
首先， 我 们 可 以 发现有 这 样一 个事实： 如 果 P是 G中 从vs到 vj的 最 短 路 ， vi是 P中的 一 个点 ， 那 么 ， 从vs沿 P到 vi的 路 是 从vs到 vi的 最 短 路
（ 一 ） Dijkstra算 法 对 于图 G， 如 果 所 有 Wij
