东北大学秦皇岛分校 数据结构课程设计 交通咨询系统设计 专 业 计算机科学与技术 班 级 姓 名 指导教师 日 期 一 、 需 求 分 析 设 计 一 个 交 通 咨 询 系 统 ，能 让 旅 客 咨 询 从 任 一 个 城 市 顶 点 到 另 一 城 市 顶 点 之 间 的 最 短 路径 （ 里 程 ） 或 最 低 花 费 或 最 少 时 间 等 问 题 。 对 于 不 同 的 咨 询 要 求 ， 可 输 入 城 市 间 的 路 程 或 所需 时 间 或 所 需 费 用 。 本 设 计 共 分 三 部 分 ， 一 是 建 立 交 通 网 络 图 的 存 储 结 构 ； 二 是 解 决 单 源 最 短 路 径 问 题 ； 三是 实 现 任 两 个 城 市 顶 点 之 间 的 最 短 路 径 问 题 。 1.1.1 建 立 图 的 存 储 结 构 邻 接 矩 阵 是 表 示 图 形 中 顶 点 之 间 相 邻 关 系 的 矩 阵 。 图 的 邻 接 矩 阵 是 定 义 如 下 的n 阶 方阵 ： 设 G=（ V， E） 是 一 个 图 ， 结 点 集 为nvvvV,,,21。 G 的 邻 接 矩 阵,E,,0E,,)(,)(jijijijinnjiijnnijvvvvvvvvwaaA） 或当 （，或） 或当 （， 当 邻 接 矩 阵 的 行 表 头 、 列 表 头 顺 序 一 定 时 ， 一 个 图 的 邻 接 矩 阵 表 示 是 唯 一 的 。 图 的 邻 接 矩 阵 表 示 ， 除 了 需 用 一 个 二 维 数 组 存 储 顶 点 之 间 的 相 邻 关 系 的 邻 接 矩 阵 外 ， 通常 还 需 要 使 用 一 个 具 有 n 个 元 素 的 一 维 数 组 来 存 储 顶 点 信 息 ，其 中 下 标 为 i 的 元 素 存 储 顶 点i 的 信 息 。 因 此 ， 图 的 邻 接 矩 阵 的 存 储 结 构 定 义 如 下 ： #definf MVNum 50 //最 大顶 点 数 typedef struct { VertexType vexs[MVNum]; //顶 点 数 组 ， 类型假定 为 char 型 Adjmatrix arcs[MVNum][MVNum]; //邻 接 矩 阵 ， 假定 为 int 型 }MGraph; 1.1.2 单 源 最 短 路 径 最 短 路 径 的 提法很多。 在这里 先讨论单 源 最 短 路 径 问 题 ： 即已知有 向图 （ 带权），...
