基于Dijkstra最短路径算法的优化研究.pdf

年 月 渭 南师 范学院学报 ．
第 卷 第 期 排 序 的 一 种 新 的优 化 方 法 ．�
� 传统 的 ��������算法�
�．� 算法 的基本 思想�
��������算 法 用 于 计 算 一 个 源 节 点 到 所 有 其 他 节 点 的 最 短 代 价 路 径 ，它 是 按 路 径 长 度 递 增 的 次 序 来 产 �
生 最 短 路 径 的 算 法 ．下 面 以 邻 接 矩 阵 描 述 ��������算 法 的实 现 过 程 ．假 设 用 带 权 的 邻 接 矩 阵 ����来 表 示 具 �
有 � 个 结 点 的 带 权 有 向 图 ���� ，������，��表 示 弧 ���，�� �的 权 值 ，如 果 从 ��到 ��不 通 ，则 ������，�
�� �� ．引进 一 个 辅 助 向 量 ����并 设 ��为 起 始 点 ，每 个 分 量 �������表 示 已 找 到 的 从 起 始 点 ��到 每 个 �
终 点 ��的 最 小 权 值 ．则 该 向 量 的 初 始 值 为 ：������� � ������，��������．其 中 ，� 是 结 点 的集 合 ．令 ��
为 已经 找 到 的 从 起 点 出 发 的 最 短 路 径 的终 点 集 合 ，初 始 值 为 � � ����，则 从 ��出 发 到 图 � 上 其 它 所 有 �
结 点 ��可 能 达 到 的 最 短 路 径 长 度 为 ������� � ������，����∈�．�
���选 择 ��，使 得 ���� ������������∈� — ��．��就 是 当 前 求 得 的 一 条 从 ��出 发 的最 短 路 径 的�
终 点 ，令 � � ��������．�
���修 改 从 ��到 集 合 � — �中任 意 一 顶 点 �� 的 最 短 路 径 长 度 ．如 果 � ��� �������，�� �� ���，�
则 进 行 第 ���步 ．�