Floyd最短路径算法的动态优化_李洪波
- 格式：pdf
- 大小：138.42 KB
- 文档页数：4
Ｆｌｏｙｄ 最短路径算法的动态优化
李洪波 １， 王茂波 ２ （ １．烟台师范学院 数学与信息学院， 山东 烟台 ２６４０２５；
２．大连理工大学 计算机系， 辽宁 大连 １１６０２３）
Ｅ－ ｍａｉｌ： ｆａｓｔ＿ｒｕｎ＿ｍａｎ＠ｓｉｎａ．ｃｏｍ
摘 要： 根据 Ｆｌｏｙｄ 最短路径算法的三层循环， 设计了动态优化新算法。动态优化新算法设计了独特的动态 ＡＶ 集合、可 发表 Ｂ 和可达表 Ａ， 分别对原算法的外层循环、中层循环和内层循环进行极小化的运算。在极小化的处理过程中， 为保证 可发表 Ｂ 和可达表 Ａ 中不存在重复元素， 引入了仅一次插入矩阵 Ｍ。动态优化新算法的时间复杂度为 Ｏ（ ｎ２＋｜ＡＶ｜×ｅ２／ｎ２） （ ｜ＡＶ｜!ｎ） ， 使得算法能够根据点数、边数和边的实际分布动态调整自身的性能。 关键词： Ｆｌｏｙｄ 最短路径； ＡＶ 集合； 可达表 Ａ； 可发表 Ｂ； 仅一次插入矩阵 Ｍ 文章编号： １００２－ ８３３１（ ２００６） ３４－ ００６０－ ０４ 文献标识码： Ａ 中图分类号： ＴＰ３３１
ｆｏｒ（ ｖ＝０； ｖ＜Ｇ．ｖｅｘｎｕｍ； ＋＋ｖ） ／／１．１ ｆｏｒ（ ｗ＝０； ｗ＜Ｇ．ｖｅｘｎｕｍ； ＋＋ｗ） ／／１．２ Ｄ［ｖ］［ｗ］＝Ｇ．ａｒｃｓ［ｖ］［ｗ］； ／／１．３ ｆｏｒ（ ｕ＝０； ｕ＜Ｇ．ｖｅｘｎｕｍ； ＋＋ｕ） ／／１．４ ｆｏｒ（ ｖ＝０； ｖ＜Ｇ．ｖｅｘｎｕｍ； ＋＋ｖ） ／／１．５
１ ∞ ０ ∞ ４ ∞ ０ ∞ ４ ∞ ０ ∞ ４ ∞ ０ ∞ ４ ∞ ０ １１ ４
２ ∞ １２ ０ ∞ ∞ １２ ０ ∞ ∞ １２ ０ １６ ∞ １２ ０ １６ ∞ １２ ０ １６
３ ∞ ∞ ７ ０ ∞ ∞ ７ ０ ∞ ∞ ７ ０ ∞ １９ ７ ０ ∞ １９ ７ ０
２．２ 动态优化算法的设计
设有向图 Ｇ＝（ Ｖ， Ｅ） ， 边数为 ｅ， 点数为 ｎ。引入一个辅助集 合 ＡＶ， ＡＶ 表示所有入度大于 ０ 的顶点集合， 当 ＡＶ 集合不空， 从中选择第一个顶点 Ｐ０（ 下标 ０ 为顶点在 ＡＶ 集合中的序号） ， 计算 Ｄ（ Ｐ０） ， 从 ＡＶ 集合中删除 Ｐ０。当 ＡＶ 集合不空， 重复上述 过程 依 次 计 算 Ｄ（Ｐ１） ， … ， Ｄ （ （Ｐ｜ＡＶ｜） ｜ＡＶ｜为 ＡＶ 集 合 中 数 据 元 素 的 个 数） ， Ｄ（Ｐ｜ＡＶ｜）［ｉ］［ｊ］就是顶点 ｉ 到顶点 ｊ 的最短路径长度。动态优化 算法也是按路径长度递增的次序产生源点到各顶点的最短路 径， 只不过每次经过的中间点必须是入度大于 ０ 的点， 避免了 无谓的循环， 这构成动态优化算法的一个方面， 即如何选择中 间点以裁减路径中不可能经过的中间点的无关循环计算， 也就 是极小化算法 １ 的 １．４ 语句的执行次数。表 ２ 是 Ｆｌｏｙｄ 最短路 径动态优化后有向图 Ｇ１ 各点对间的最短路径求解过程。
若＜ｖｉ， ｖｊ＞存在， 则存在路径｛ｖｉ， ｖｊ｝（ 路径中不含其它顶点） ； 若＜ｖｉ， ｖ１＞， ＜ｖ１， ｖｊ＞存 在 ， 则 存 在 路 径｛ｖｉ， ｖ１， ｖｊ｝（ 路 径 中 所 含 顶点序号不大于 １） ； 若｛ｖｉ， …， ｖ２｝， ｛ｖ２， …， ｖｊ｝存在， 则存在一条路径｛ｖｉ， …， ｖ２， …， ｖｊ｝ （ 路径中所含顶点序号不大于 ２） 。 依次类推， 则 ｖｉ 到 ｖｊ 的 最 短 路 径 应 是 上 述 这 些 路 径 中 ， 路 径长度最小者。 现 定 义 一 个 ｎ 阶 方 阵 序 列 Ｄ（－１）， Ｄ（０）， Ｄ（１）， … ， Ｄ（ｋ）， … ， Ｄ ， （ｎ－１） 其中： Ｄ（ － １） ［ｉ］［ｊ］＝Ｇ．ａｒｃｓ［ｉ］［ｊ］ Ｄ（ｋ）［ｉ］［ｊ］＝Ｍｉｎ｛Ｄ（ｋ－１）［ｉ］［ｊ］， Ｄ（ｋ－１）［ｉ］［ｋ］＋Ｄ（ｋ－１）［ｋ］［ｊ］｝ ０!ｋ!ｎ－ １ 从 上 述 计 算 公 式 可 见 ， Ｄ（１） ［ｉ］［ｊ］是 从 ｖｉ 到 ｖｊ 的 中 间 顶 点 的 序 号 不 大 于 １ 的 最 短 路 径 长 度 ； Ｄ（ｋ）［ｉ］［ｊ］是 从 ｖｉ 到 ｖｊ 的 中 间 顶 点的序号不大于 ｋ 的最短路径长度 ； Ｄ（ｎ－１）［ｉ］［ｊ］是 从 ｖｉ 到 ｖｊ 的 最 短路径长度。Ｆｌｏｙｄ 最短路径算法（ 算法 １） 的 Ｃ 语言描述如下： ｖｏｉｄ ＳｈｏｒｅｓｔＰａｔｈ＿ＦＬＯＹＤ（ ＭＧｒａｐｈ Ｇ， ＤｉｓｔａｎｃｅＭａｔｒｉｘ ＆Ｄ） ｛
６
Ｖ０
Ｖ１
１２
１６
４
Ｖ２
Ｖ３
７
图 １ 带权有向图 Ｇ１
Ｆｌｏｙｄ 算法 １ 的执行过程如表 １ 所示。显然， 其循环语句的 执行频度为 ４３＋４２＝８０。观察图 １ 不难发现， Ｖ０ 顶点入度为 ０， 它 不会成为任何点对间最短路径的中间点， 应该避免这样无关的 循环； 另一方面， 当 Ｖ１、Ｖ２ 或 Ｖ３ 依次作为中 间 点 求 解 最 短 路 径
ｆｏｒ（ ｗ＝０； ｗ＜Ｇ．ｖｅｘｎｕｍ； ＋＋ｗ） ／／１．６ ｉｆ（ Ｄ［ｖ］［ｕ］＋Ｄ［ｕ］［ｗ］＜Ｄ［ｖ］［ｗ］） ｛ ／／１．７ Ｄ［ｖ］［ｗ］＝Ｄ［ｖ］［ｕ］＋Ｄ［ｕ］［ｗ］； ／／１．８ ｝
｝ 在 算 法 １ 中 ， ＭＧｒａｐｈ 是 图 的 邻 接 矩 阵 存 储 结 构 体 类 型 ， ＤｉｓｔａｎｃｅＭａｔｒｉｘ 是距离矩阵二维数组类型， 详见参考文献［１］。算 法 １ 语句执行频度为 ｎ３＋ｎ２， 时间复杂度为 Ｏ（ ｎ３） 。显然， 算法 １ 的缺陷是时间开销为点数的多项式函数， 而不管该图是否存在 边。进一步， 对于具有 ｎ 个孤立顶点没有弧的图， Ｆｌｏｙｄ 最短路 径 算 法 处 理 的 时 间 开 销 是 ｎ３＋ｎ２， 而 不 是 接 近 于 ０。 为 此 ， 对 Ｆｌｏｙｄ 最短路径算法进行改进， 使其能够根据依赖于弧头的点 数做出动态的调整。举例说明一般的有向图算法 １ 的执行过程。 例： 设图 Ｇ１＝（ Ｖ１， Ｅ１） ， Ｖ１＝｛ｖ１， ｖ２， ｖ３， ｖ４， ｖ５｝， Ｅ１＝｛＜ｖ１， ｖ２＞， ＜ｖ１， ｖ４＞， ＜ｖ２， ｖ４＞， ＜ｖ４， ｖ３＞， ＜ｖ３， ｖ２＞｝， 如图 １ 所示。求图上所有点对间 的最短路径。
作者简介： 李洪波（ １９６９－ ） ， 男， 讲师， 主要研究方向： 算法分析与设计、数据挖掘、并行计算。 ６０ ２００６．３４ 计算机工程与应用
２ Ｆｌｏｙｄ 最短路径算法的动态优化 ２．１ Ｆｌｏｙｄ 最短路径算法简介
为便于比较， 先简要介绍 Ｆｌｏｙｄ 算 法 ， 详 见 参 考 文 献［１］。 Ｆｌｏｙｄ 算法仍从图的带权邻接矩阵 ｃｏｓｔ 出发， 其基本思想是从 ｖｉ 到 ｖｊ 的最短路径是以下各种可能路径中的长度最小者：
时， 应根据其实际的连线情况进行最小化的判断。
表 １ 有向图 Ｇ１ 各点对间的最短路径求解过程
（ － １）
Ｄ
（ ０）
Ｄ
（ １）
Ｄ
（ ２）
Ｄ
（ ３）
Ｄ
ＤБайду номын сангаас
０ １２３０１２３０１２３ ０ １ ２ ３ ０ １ ２ ３
０ ０ ６ ∞ １６ ０ ６ ∞ １６ ０ ６ ∞ １０ ０ ６ ∞ １０ ０ ６ １７ １０
１ 引言
单源点最短路径问题是给定带权有向图 Ｇ 和源点 ｖ， 求从 ｖ 到 Ｇ 中其余各顶点的最短路径。Ｄｉｊｋｓｔｒａ 提 出 了 一 个 按 最 短 路径递增的次序产生最短路径的算法， 其时间开销为 ２ｎ（ ｎ－ １） ＋ｎ（ ｎ 为图 Ｇ 的顶点个数） 。如果求所有点对间的最短路径， 解 决这个问题的一个方法是： 每次以一个顶点为源点， 重复执行 Ｄｉｊｋｓｔｒａ 算法 ｎ 次， 这样便可求得每一对顶点间的最短路径。总 的执 行 时 间 为 Ｏ（ ｎ３） 。Ｆｌｏｙｄ 提 出 了 解 决 每 一 对 顶 点 间 最 短 路 径的一个方法， 该方法形式上更简洁些， 但其总的执行时间为 Ｏ（ ｎ３） 。这两种方案的缺陷是时间开销为点数 ｎ 的多项式， 不能 根 据 图 的 边 数 、边 的 实 际 分 布 和 点 数 联 合 动 态 调 整 算 法 本 身 的 时间开销， 以使得算法的运行时间极小化， 运算速度极大化。
Ｙａｎｔａｉ， Ｓｈａｎｄｏｎｇ ２６４０２５， Ｃｈｉｎａ； ２．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｄａｌｉａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ
Ｔｅｃｈｎｏｌｏｇｙ， Ｄａｌｉａｎ， Ｌｉａｏｎｉｎｇ １１６０２３， Ｃｈｉｎａ）
Ａｂｓｔｒ ａｃｔ： Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｔｈｒｅｅ ｌａｙｅｒｓ’ｃｙｃｌｅ ｏｆ ｔｈｅ ｆｌｏｙｄ ｓｈｏｒｔｅｓｔ ｐａｔｈ’ｓ ａｌｇｏｒｉｔｈｍ， ｄｅｓｉｇｎ ｄｙｎａｍｉｃ ｏｐｔｉｍｕｍ ｎｅｗ ａｌ－ ｇｏｒｉｔｈｍ．Ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｄｅｖｉｓｅｓ ａｎ ｕｎｉｑｕｅ ｄｙｎａｍｉｃ ＡＶ ａｇｇｒｅｇａｔｅ， ａ ｒｅａｃｈａｂｌｅ ｔａｂｌｅ Ａ ａｎｄ ａ ｓｔａｒｔｉｎｇ－ ｏｆｆ ｔａｂｌｅ Ｂ， ｓｅｐａｒａｔｅｌｙ ｔｏ ｐｒｏｃｅｅｄ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｔｈｅ ｅｘｔｅｒｉｏｒ ｌａｙｅｒ， ｍｉｄｄｌｅ ｌａｙｅｒ ａｎｄ ｉｎｎｅｒ ｌａｙｅｒ ｗｉｔｈ ｍｉｎｉｍｕｍ ｏｐｅｒａｔｉｏｎ．Ｉｎ ｔｈｅ ｐｒｏ－ ｃｅｓｓ ｏｆ ｔｈｅ ｍｉｎｉｍｕｍ ｏｐｅｒａｔｉｏｎ， ｉｎ ｏｒｄｅｒ ｔｏ ｅｌｉｍｉｎａｔｅ ｔｈｅ ｒｅｐｅｔｉｔｉｏｎ ｉｎ ｅｖｅｒｙ ｑｕｅｕｅ ｏｆ ｒｅａｃｈａｂｌｅ ｔａｂｌｅ Ａ ａｎｄ ｓｔａｒｔｉｎｇ ｏｆｆ－ ｔａｂｌｅ Ｂ， ｉｎｔｒｏｄｕｃｅｓ ａ ｏｎｌｙ ｏｎｃｅ ａｄｄｅｄ ａｒｒａｙ Ｍ．Ｔｈｅ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｄｙｎａｍｉｃ ｏｐｔｉｍｕｍ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｉｓ Ｏ（ ｎ２＋｜ＡＶ｜×ｅ２／ｎ２） （ ｜ＡＶ｜!ｎ） ， ｗｈｉｃｈ ｉｓ ａｂｌｅ ｔｏ ａｄｊｕｓｔ ｉｔｓ ｐｅｒｆｏｒｍａｎｃｅ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｎｕｍｂｅｒ ｖｅｒｔｅｘ， ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｅｄｇｅ ａｎｄ ｔｈｅ ｒｅａｌ ｄｉｓｔｒｉｂｕｔｉｎｇ ｏｆ ｅｄｇｅ． Ｋｅｙ ｗｏｒ ｄｓ： Ｆｌｏｙｄ ｓｈｏｒｔｅｓｔ ｐａｔｈ； ＡＶ ａｇｇｒｅｇａｔｅ； ｒｅａｃｈａｂｌｅ ｔａｂｌｅ Ａ； ｓｔａｒｔｉｎｇ－ ｏｆｆ ｔａｂｌｅ Ｂ； ｏｎｌｙ ｏｎｃｅ ａｄｄｅｄ ａｒｒａｙ Ｍ
李洪波 １， 王茂波 ２ （ １．烟台师范学院 数学与信息学院， 山东 烟台 ２６４０２５；
２．大连理工大学 计算机系， 辽宁 大连 １１６０２３）
Ｅ－ ｍａｉｌ： ｆａｓｔ＿ｒｕｎ＿ｍａｎ＠ｓｉｎａ．ｃｏｍ
摘 要： 根据 Ｆｌｏｙｄ 最短路径算法的三层循环， 设计了动态优化新算法。动态优化新算法设计了独特的动态 ＡＶ 集合、可 发表 Ｂ 和可达表 Ａ， 分别对原算法的外层循环、中层循环和内层循环进行极小化的运算。在极小化的处理过程中， 为保证 可发表 Ｂ 和可达表 Ａ 中不存在重复元素， 引入了仅一次插入矩阵 Ｍ。动态优化新算法的时间复杂度为 Ｏ（ ｎ２＋｜ＡＶ｜×ｅ２／ｎ２） （ ｜ＡＶ｜!ｎ） ， 使得算法能够根据点数、边数和边的实际分布动态调整自身的性能。 关键词： Ｆｌｏｙｄ 最短路径； ＡＶ 集合； 可达表 Ａ； 可发表 Ｂ； 仅一次插入矩阵 Ｍ 文章编号： １００２－ ８３３１（ ２００６） ３４－ ００６０－ ０４ 文献标识码： Ａ 中图分类号： ＴＰ３３１
ｆｏｒ（ ｖ＝０； ｖ＜Ｇ．ｖｅｘｎｕｍ； ＋＋ｖ） ／／１．１ ｆｏｒ（ ｗ＝０； ｗ＜Ｇ．ｖｅｘｎｕｍ； ＋＋ｗ） ／／１．２ Ｄ［ｖ］［ｗ］＝Ｇ．ａｒｃｓ［ｖ］［ｗ］； ／／１．３ ｆｏｒ（ ｕ＝０； ｕ＜Ｇ．ｖｅｘｎｕｍ； ＋＋ｕ） ／／１．４ ｆｏｒ（ ｖ＝０； ｖ＜Ｇ．ｖｅｘｎｕｍ； ＋＋ｖ） ／／１．５
１ ∞ ０ ∞ ４ ∞ ０ ∞ ４ ∞ ０ ∞ ４ ∞ ０ ∞ ４ ∞ ０ １１ ４
２ ∞ １２ ０ ∞ ∞ １２ ０ ∞ ∞ １２ ０ １６ ∞ １２ ０ １６ ∞ １２ ０ １６
３ ∞ ∞ ７ ０ ∞ ∞ ７ ０ ∞ ∞ ７ ０ ∞ １９ ７ ０ ∞ １９ ７ ０
２．２ 动态优化算法的设计
设有向图 Ｇ＝（ Ｖ， Ｅ） ， 边数为 ｅ， 点数为 ｎ。引入一个辅助集 合 ＡＶ， ＡＶ 表示所有入度大于 ０ 的顶点集合， 当 ＡＶ 集合不空， 从中选择第一个顶点 Ｐ０（ 下标 ０ 为顶点在 ＡＶ 集合中的序号） ， 计算 Ｄ（ Ｐ０） ， 从 ＡＶ 集合中删除 Ｐ０。当 ＡＶ 集合不空， 重复上述 过程 依 次 计 算 Ｄ（Ｐ１） ， … ， Ｄ （ （Ｐ｜ＡＶ｜） ｜ＡＶ｜为 ＡＶ 集 合 中 数 据 元 素 的 个 数） ， Ｄ（Ｐ｜ＡＶ｜）［ｉ］［ｊ］就是顶点 ｉ 到顶点 ｊ 的最短路径长度。动态优化 算法也是按路径长度递增的次序产生源点到各顶点的最短路 径， 只不过每次经过的中间点必须是入度大于 ０ 的点， 避免了 无谓的循环， 这构成动态优化算法的一个方面， 即如何选择中 间点以裁减路径中不可能经过的中间点的无关循环计算， 也就 是极小化算法 １ 的 １．４ 语句的执行次数。表 ２ 是 Ｆｌｏｙｄ 最短路 径动态优化后有向图 Ｇ１ 各点对间的最短路径求解过程。
若＜ｖｉ， ｖｊ＞存在， 则存在路径｛ｖｉ， ｖｊ｝（ 路径中不含其它顶点） ； 若＜ｖｉ， ｖ１＞， ＜ｖ１， ｖｊ＞存 在 ， 则 存 在 路 径｛ｖｉ， ｖ１， ｖｊ｝（ 路 径 中 所 含 顶点序号不大于 １） ； 若｛ｖｉ， …， ｖ２｝， ｛ｖ２， …， ｖｊ｝存在， 则存在一条路径｛ｖｉ， …， ｖ２， …， ｖｊ｝ （ 路径中所含顶点序号不大于 ２） 。 依次类推， 则 ｖｉ 到 ｖｊ 的 最 短 路 径 应 是 上 述 这 些 路 径 中 ， 路 径长度最小者。 现 定 义 一 个 ｎ 阶 方 阵 序 列 Ｄ（－１）， Ｄ（０）， Ｄ（１）， … ， Ｄ（ｋ）， … ， Ｄ ， （ｎ－１） 其中： Ｄ（ － １） ［ｉ］［ｊ］＝Ｇ．ａｒｃｓ［ｉ］［ｊ］ Ｄ（ｋ）［ｉ］［ｊ］＝Ｍｉｎ｛Ｄ（ｋ－１）［ｉ］［ｊ］， Ｄ（ｋ－１）［ｉ］［ｋ］＋Ｄ（ｋ－１）［ｋ］［ｊ］｝ ０!ｋ!ｎ－ １ 从 上 述 计 算 公 式 可 见 ， Ｄ（１） ［ｉ］［ｊ］是 从 ｖｉ 到 ｖｊ 的 中 间 顶 点 的 序 号 不 大 于 １ 的 最 短 路 径 长 度 ； Ｄ（ｋ）［ｉ］［ｊ］是 从 ｖｉ 到 ｖｊ 的 中 间 顶 点的序号不大于 ｋ 的最短路径长度 ； Ｄ（ｎ－１）［ｉ］［ｊ］是 从 ｖｉ 到 ｖｊ 的 最 短路径长度。Ｆｌｏｙｄ 最短路径算法（ 算法 １） 的 Ｃ 语言描述如下： ｖｏｉｄ ＳｈｏｒｅｓｔＰａｔｈ＿ＦＬＯＹＤ（ ＭＧｒａｐｈ Ｇ， ＤｉｓｔａｎｃｅＭａｔｒｉｘ ＆Ｄ） ｛
６
Ｖ０
Ｖ１
１２
１６
４
Ｖ２
Ｖ３
７
图 １ 带权有向图 Ｇ１
Ｆｌｏｙｄ 算法 １ 的执行过程如表 １ 所示。显然， 其循环语句的 执行频度为 ４３＋４２＝８０。观察图 １ 不难发现， Ｖ０ 顶点入度为 ０， 它 不会成为任何点对间最短路径的中间点， 应该避免这样无关的 循环； 另一方面， 当 Ｖ１、Ｖ２ 或 Ｖ３ 依次作为中 间 点 求 解 最 短 路 径
ｆｏｒ（ ｗ＝０； ｗ＜Ｇ．ｖｅｘｎｕｍ； ＋＋ｗ） ／／１．６ ｉｆ（ Ｄ［ｖ］［ｕ］＋Ｄ［ｕ］［ｗ］＜Ｄ［ｖ］［ｗ］） ｛ ／／１．７ Ｄ［ｖ］［ｗ］＝Ｄ［ｖ］［ｕ］＋Ｄ［ｕ］［ｗ］； ／／１．８ ｝
｝ 在 算 法 １ 中 ， ＭＧｒａｐｈ 是 图 的 邻 接 矩 阵 存 储 结 构 体 类 型 ， ＤｉｓｔａｎｃｅＭａｔｒｉｘ 是距离矩阵二维数组类型， 详见参考文献［１］。算 法 １ 语句执行频度为 ｎ３＋ｎ２， 时间复杂度为 Ｏ（ ｎ３） 。显然， 算法 １ 的缺陷是时间开销为点数的多项式函数， 而不管该图是否存在 边。进一步， 对于具有 ｎ 个孤立顶点没有弧的图， Ｆｌｏｙｄ 最短路 径 算 法 处 理 的 时 间 开 销 是 ｎ３＋ｎ２， 而 不 是 接 近 于 ０。 为 此 ， 对 Ｆｌｏｙｄ 最短路径算法进行改进， 使其能够根据依赖于弧头的点 数做出动态的调整。举例说明一般的有向图算法 １ 的执行过程。 例： 设图 Ｇ１＝（ Ｖ１， Ｅ１） ， Ｖ１＝｛ｖ１， ｖ２， ｖ３， ｖ４， ｖ５｝， Ｅ１＝｛＜ｖ１， ｖ２＞， ＜ｖ１， ｖ４＞， ＜ｖ２， ｖ４＞， ＜ｖ４， ｖ３＞， ＜ｖ３， ｖ２＞｝， 如图 １ 所示。求图上所有点对间 的最短路径。
作者简介： 李洪波（ １９６９－ ） ， 男， 讲师， 主要研究方向： 算法分析与设计、数据挖掘、并行计算。 ６０ ２００６．３４ 计算机工程与应用
２ Ｆｌｏｙｄ 最短路径算法的动态优化 ２．１ Ｆｌｏｙｄ 最短路径算法简介
为便于比较， 先简要介绍 Ｆｌｏｙｄ 算 法 ， 详 见 参 考 文 献［１］。 Ｆｌｏｙｄ 算法仍从图的带权邻接矩阵 ｃｏｓｔ 出发， 其基本思想是从 ｖｉ 到 ｖｊ 的最短路径是以下各种可能路径中的长度最小者：
时， 应根据其实际的连线情况进行最小化的判断。
表 １ 有向图 Ｇ１ 各点对间的最短路径求解过程
（ － １）
Ｄ
（ ０）
Ｄ
（ １）
Ｄ
（ ２）
Ｄ
（ ３）
Ｄ
ＤБайду номын сангаас
０ １２３０１２３０１２３ ０ １ ２ ３ ０ １ ２ ３
０ ０ ６ ∞ １６ ０ ６ ∞ １６ ０ ６ ∞ １０ ０ ６ ∞ １０ ０ ６ １７ １０
１ 引言
单源点最短路径问题是给定带权有向图 Ｇ 和源点 ｖ， 求从 ｖ 到 Ｇ 中其余各顶点的最短路径。Ｄｉｊｋｓｔｒａ 提 出 了 一 个 按 最 短 路径递增的次序产生最短路径的算法， 其时间开销为 ２ｎ（ ｎ－ １） ＋ｎ（ ｎ 为图 Ｇ 的顶点个数） 。如果求所有点对间的最短路径， 解 决这个问题的一个方法是： 每次以一个顶点为源点， 重复执行 Ｄｉｊｋｓｔｒａ 算法 ｎ 次， 这样便可求得每一对顶点间的最短路径。总 的执 行 时 间 为 Ｏ（ ｎ３） 。Ｆｌｏｙｄ 提 出 了 解 决 每 一 对 顶 点 间 最 短 路 径的一个方法， 该方法形式上更简洁些， 但其总的执行时间为 Ｏ（ ｎ３） 。这两种方案的缺陷是时间开销为点数 ｎ 的多项式， 不能 根 据 图 的 边 数 、边 的 实 际 分 布 和 点 数 联 合 动 态 调 整 算 法 本 身 的 时间开销， 以使得算法的运行时间极小化， 运算速度极大化。
Ｙａｎｔａｉ， Ｓｈａｎｄｏｎｇ ２６４０２５， Ｃｈｉｎａ； ２．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｄａｌｉａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ
Ｔｅｃｈｎｏｌｏｇｙ， Ｄａｌｉａｎ， Ｌｉａｏｎｉｎｇ １１６０２３， Ｃｈｉｎａ）
Ａｂｓｔｒ ａｃｔ： Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｔｈｒｅｅ ｌａｙｅｒｓ’ｃｙｃｌｅ ｏｆ ｔｈｅ ｆｌｏｙｄ ｓｈｏｒｔｅｓｔ ｐａｔｈ’ｓ ａｌｇｏｒｉｔｈｍ， ｄｅｓｉｇｎ ｄｙｎａｍｉｃ ｏｐｔｉｍｕｍ ｎｅｗ ａｌ－ ｇｏｒｉｔｈｍ．Ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｄｅｖｉｓｅｓ ａｎ ｕｎｉｑｕｅ ｄｙｎａｍｉｃ ＡＶ ａｇｇｒｅｇａｔｅ， ａ ｒｅａｃｈａｂｌｅ ｔａｂｌｅ Ａ ａｎｄ ａ ｓｔａｒｔｉｎｇ－ ｏｆｆ ｔａｂｌｅ Ｂ， ｓｅｐａｒａｔｅｌｙ ｔｏ ｐｒｏｃｅｅｄ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｔｈｅ ｅｘｔｅｒｉｏｒ ｌａｙｅｒ， ｍｉｄｄｌｅ ｌａｙｅｒ ａｎｄ ｉｎｎｅｒ ｌａｙｅｒ ｗｉｔｈ ｍｉｎｉｍｕｍ ｏｐｅｒａｔｉｏｎ．Ｉｎ ｔｈｅ ｐｒｏ－ ｃｅｓｓ ｏｆ ｔｈｅ ｍｉｎｉｍｕｍ ｏｐｅｒａｔｉｏｎ， ｉｎ ｏｒｄｅｒ ｔｏ ｅｌｉｍｉｎａｔｅ ｔｈｅ ｒｅｐｅｔｉｔｉｏｎ ｉｎ ｅｖｅｒｙ ｑｕｅｕｅ ｏｆ ｒｅａｃｈａｂｌｅ ｔａｂｌｅ Ａ ａｎｄ ｓｔａｒｔｉｎｇ ｏｆｆ－ ｔａｂｌｅ Ｂ， ｉｎｔｒｏｄｕｃｅｓ ａ ｏｎｌｙ ｏｎｃｅ ａｄｄｅｄ ａｒｒａｙ Ｍ．Ｔｈｅ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｄｙｎａｍｉｃ ｏｐｔｉｍｕｍ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｉｓ Ｏ（ ｎ２＋｜ＡＶ｜×ｅ２／ｎ２） （ ｜ＡＶ｜!ｎ） ， ｗｈｉｃｈ ｉｓ ａｂｌｅ ｔｏ ａｄｊｕｓｔ ｉｔｓ ｐｅｒｆｏｒｍａｎｃｅ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｎｕｍｂｅｒ ｖｅｒｔｅｘ， ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｅｄｇｅ ａｎｄ ｔｈｅ ｒｅａｌ ｄｉｓｔｒｉｂｕｔｉｎｇ ｏｆ ｅｄｇｅ． Ｋｅｙ ｗｏｒ ｄｓ： Ｆｌｏｙｄ ｓｈｏｒｔｅｓｔ ｐａｔｈ； ＡＶ ａｇｇｒｅｇａｔｅ； ｒｅａｃｈａｂｌｅ ｔａｂｌｅ Ａ； ｓｔａｒｔｉｎｇ－ ｏｆｆ ｔａｂｌｅ Ｂ； ｏｎｌｙ ｏｎｃｅ ａｄｄｅｄ ａｒｒａｙ Ｍ
