维普资讯 http://www.cqvip.com ２００８年第２期 福建电脑 ９ 几种最短路径的算法及比较 刘文海 ．徐荣聪 （１．福建时外经济贸易职业技术学院福建福州３５００１６ ２．福州大学数学与计算机科学学院福建福州３５０００２） 【摘要】：最短路径问题是图论中一个非常有实际意义的问题，在实际生活中的各种规划设计问题中及数据挖掘中都 有重要的作用。本文着重介绍了用计算机编程语言实现单源最短路径算法与每对结点问的最短路径算法，并作了简单比较。 【关键宇】：Ｒｅｌａｘ Ｄｉｊｋｓｔｒａ Ｂｅｌｌｍａｎ有向无环图上的最短路Ｆｌｏｙｄ—Ｗａｒｓｈａｌｌ Ｊｏｈｎｓｏｎ １．引言 ２＿３．１算法描述 对于每一结点ｓ ＥＳ．逐步减小从源Ｓ到ｖ的最短路径估计 为了方便我们对最短路径问题的研究．下面给出其定义。 定义：在最短路径问题中，给出的是一张有向加权图Ｇ＝ｆｖ， ｄＭ直至其到达实际最短路径的权。最多进行ＩＶ【Ｇ１Ｉ一１次松弛操 Ｅ１．在其上定义的加权函数ｗ：Ｅ—Ｒ为边到实型权值的映射。路 作。算法返回Ｔｒｕｅ当且仅当图中不存在负权圈。 ２＿３．２算法分析 径Ｐ＝ ％… 的权指的是其组成边的所有权值之和： 该算法的时间复杂度为０（ＶＥ）。 ｗ（ｐ）＝ ｗ（ ．Ｉ，Ｖ，） ２．３．３算法优化 该算法名为Ｓｈｏｒｔｅｓｔ ｐａｔｈ ｆａｓｔｅｒ ａｌｇｏｒｉｔｈｍ ．ＳＰＦＡ其实就是 Ｂｅｌｌｍａｎ—Ｆｏｒｄ的一种队列实现．减少了冗余，即松驰的边至少不 定义从ｕ到 的最短路径的权为： 讹ｖ）＝仨ｉＩ∞ Ｉｌ ２．单源最短路径算法 ２．１松弛技术（Ｒｅｌａｘ）ｆ。１ 到 ｌ 通 会以一个ｄ为 的点为起点。 ２．３．４复杂度分析 ＳＰＦＡ在形式上和宽度优先搜索非常类似．不同的是宽度优 单源最短路径问题所求的是：从某结点ｓ到其它所有结点 先搜索中一个点出了队列就不可能重新进入队列．但是ＳＰＦＡ 的最短路径。这是最短路径问题的基础问题。其它的最短路径问 中一个点可能在出队列之后再次被放入队列．也就是一个点改 题都可以转化为单源最短路径问题进行求解。 进过其它的点之后．过了一段时间可能本身被改进．于是再次用 在每个单源最短路径算法中都运用了松弛技术。松弛一条 边就是试图找到一条比当前已知路径更短的边。对每一结点 ＥＳ，我们用卿７来表示从源ｓ到 当前已知的最短路径的权的 上界。称之为最短路径估计。用ｐ，ｅＭ￣表示当前最短路径估计 中 前面的点 松弛一条边 ）的过程包括测试我们是否可能通过结点Ｕ 对迄今找出的到Ｖ的最短路径估计进行改进．如果可能则更新 ｐｒｅ［ｖ］。 注意：单源最短路径的每个算法都要先调用初始化过程．然 ４．１算法描述 后重复松弛过程 本质就是用动态规划： ２．２ Ｄｉｉｋｓｔｒａ算法闭 来改进其它的点．这样反复迭代下去。设一个点用来作为迭代点 对其它点进行改进的平均次数为ｋ，有办法证明对于通常的（不 含负圈，较稀疏）情况，ｋ在２左右。算法复杂度理论上同Ｂｅｌ１． ｍａｎ—Ｆｏｒｄ，０ Ｅ），但实际上却是０（ｋＥ）。 ４．每对结点间的最短路径算法 最直接的方法是把每个结点都作为源做一次单源最短路径 算法，我们用ｎ０ｙｄ—Ｗａｒｓｈａｌｌ算法来解决这类问题。Ｆｌｏｙｄ算法 是一种用来解决关于图Ｇ（ｖ．Ｅ１间每对结点问的最短路径问题的 算法，可以存在负权边，但我们假定不存在负权圈。 ＧＩＪ’ｆｕ：ｕ】＝Ｏｆｕ∈、，１ Ｄｉｊｋｓｔｒａ算法解决了有向加权图的最短路径问题．它可以解 决单源最短路径问题．如果以每个点作为源都做一次Ｄｉｊｋｓｔｍ算 Ｇ （ｕ；ｖ）＝ｗ（ｕ，ｖ）（ｕ，ｖ∈Ｖ） Ｇ ”（Ｉｌ，ｖ）＝ｍｉｎ｛Ｇ （ｕ，ｖ），Ｇ （ｕ，ｋ）＋Ｇ Ｏ ｖ）｝（ｕ，Ｖ∈Ｖ’ｌ（＝ｌ，２，．．．，Ｖ－１） 法，则可以求出每对结点问的最短路径。该算法的条件是所有边 的权值都非负．这个重要的条件使得我们用贪心得到该算法。 ２．２．１算法描述 Ｇ‘ 表示ｕ到 的不经过 ，ｋ＋ｌ，．．．，，ｌ结点 ｕ，ｖ外 时，从 设置一结点集合５．从源ｓ到集合５中所有点的最短路径 ｕ到 的最短路长。下面用归纳法证明： 均已求出。算法反复挑选出最短路径估计为最小的结点ｕ加入 ｋ＝ｌ显然成立。 ５集合，并对所有离开结点ｕ的边进行松弛操作．直到所有结点 假设对ｋ成立，下面考虑ｋ＋ｌ的情况： 进入集合。 ２．２．２算法分析 从ｕ到 且不通过ｋ＋１．．．．，，ｌ 节点的最短路有两种可能：（１）不经过ｋ节点，即为Ｇ‘ ； 这里的Ｄ要用优先队列实现，需用到删除最小（ＤｅｌｅｔｅＭｉｎ１ （２）经过ｋ节点，即为Ｇ‘ Ｇ‘ 与减值（ＤｅｃｒｅａｓｅＫｅｙ）的操作。假设用普通的队列实现则算法复 由于第ｋ＋１次迭代过程中，不会影响ｋ次的迭代结果，使用 杂度为０ｆｖ 。如果用Ｆｉｂｏｎａｅｅｉ堆来实现优先队列则算法复杂 ｏ（ｖ：３￣Ｊ空间即可。二维数组ｐｒｅ（ｕ，ｖ），记录ｕ到 ，最后经过哪个 度为Ｏ（ＩＥＩ＋ＩＶＩＩｇｌＶＩ）。 ｋ的迭代。 ２．３ ＢｅｌＩＭａｎ－Ｆｏｒｄ算法闭 ４．２算法分析 如果一个图包含负权圈。那么这个图就不存在最短路径。在 时间复杂度为０ ３），空间复杂度为０ 。 Ｄｉｊｋｓｔｒａ算法中我们假定不存在负权边．而在ＢｅＵｍａｎ—Ｆｏｒｄ算法 ５．Ｊｏｈｎｓｏｎ算法 中则可以存在负权边：找到从源ｓ到所有点的最短路径或确定 ５．１算法描述 存在负权圈 本算法适用于稀疏图。它是Ｄｉｊｋｓｔｒａ和Ｂｅｌｎａｈｎ—Ｆｏｒｄ算法 （下转第２０页） 基金资助项目：福建省教育厅基金（ＪＢｏ４ｏ３６） 维普资讯 http://www.cqvip.com 福建电脑 ２００８年第２期 口 及兴趣度的向量ｏ（ａ 如以… Ｊ。其次，统计每一个兴趣项 ｖ和ｕ分别是权重因子，且口＋ｌ‘＝Ｊ。它们可以通过机器学习 在文档中出现的次数ｆｊ，从而构造出用户的兴趣项在文档中出 得到或通过经验取值。 是用户兴趣模型中该兴趣项的兴趣度 现的词频向量 ＾ｔ ｂ…ｔ＾Ｊ。最后根据如下公式，算出文档与用户 原值 兴趣的相似度Ｓ： （３）对于那些长期未被更新过的兴趣项，按照如下公式降低其对 ∑ ×ｆｊ 上 ——一 应用的兴趣度： …… …（ａ×鲁 》 首先，根据用户的兴趣模型构造用户兴趣项的向量Ｑ（ｑ ％ ＝” Ｄｊ 州ｌ一薏老 一‰ Ｄｔ．：ｄｔ，当Ｄ。 ｎ｜一Ｄｃ ＜ Ｑ ∑ｆ』 ｊ ｉ＝１ ５．采用用户兴趣模型向用户推荐信息 信息推荐Ａｇｅｎｔ的主要功能是主动搜索网上资源并向用户 其中，ｄｊ是该兴趣项原来的兴趣度，Ｄｄ一是系统当前日期， 推荐信息。首先，它以用户兴趣模型中兴趣度较高的部分兴趣 是该兴趣项最后一次被更新的日期， 是该兴趣项创建 项，通过现有的搜索引擎搜索信息。其次。启动信息过滤Ａｇｅｎｔ 出的日期， —。 表示到目前为止该兴趣项未曾被更新过的 对搜索到的信息进行过滤。最后，把过滤后的信息推荐给用户 天数， 一一 表示到目前为止该兴趣项已在库中存在的天 ６．小结 数。 本文讨论了应用Ａｇｅｎｔ技术来实现在Ｗｅｂ客户端的个性 （４）由于用户兴趣模型空问是有限的。用户兴趣模型有一个 化服务。智能Ａｇｅｎｔ通过学习来建立用户兴趣模型．并以此模型 最大的兴趣项容量，当兴趣项超过这个最大容量时，将模型中的 来实现个性化的服务：对用户搜索的信息进行过滤．提高搜索的 些低兴趣度的兴趣项删除。使兴趣项固定在某一范围。从而实 精确度；主动向用户推荐信息。 现对用户兴趣的动态追踪 ４．采用用户兴趣模型对用户检索的信息进行过滤 参考文献： 信息过滤Ａｇｅｎｔ根据用户兴趣模型对从搜索引擎返回的结 １．Ｙ．Ｓｅｏ ａｎｄ Ｂ．Ｚｈａｎｇ，Ｐｅｒｓｏｎａｌｉｚｅｄ ｗｅｂ—ｄｏｃｕｍｅｎｔ ｆｉｌｔｅｒｉｎｇ ｕｓｉｎｇ ｒｅｉｎ－ ￣ｏｒｃｅｍｅｎｔ ｌｅａｒｎｉｎｇ．Ａ ｅｄ Ａｒｆｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００１． 果进行过滤，使得这个搜索结果尽可能精确地符合用户的需求。 婉克娟李晋宏，应用Ａｇｅｎｔ技术实现个性化信息服务ｏ】．北方工业大 这个过滤主要是通过计算检索到的文档与用户兴趣的相似度． ２．学学报。Ｖｏ１．１６ Ｎｏ ３ Ｓｅｐｔ．２００４． 得到文档与用户兴趣相关的程度．将相似度超过一定闭值的文 ３．殷信义刘锦高等，智能网站Ａｇｅｎｔｓ￣ｒｍｌｊ］．计算机应用研究，２００２。第１ 档推荐给用户 一期：４２－４３。 （上接第９页） 的综合应用 算法 时闻复杂度 特殊敫据结构 使用范圈 本算法用了权值改造 ｗｅｉｇｈｔｉｎ 技术。若图的权值非负，则 对于每个结点用一次Ｄｉｊｋｓｔｒａ算法．就可以求出所有顶点对间最 短路。若图中有负权，但没有负圈，则可以把权值Ｗ改造成Ｗ ， Ｗ 非负，使得能够使用Ｄｉｉｌ【ｓｔｒａ算法 Ｄｉｊｍｒａ Ｂｅｌｌｍａｎ Ｆｌｏｙｄ Ｊｏｈｎｓｏ￣ ｏ（吲＋Ｉｖ ｖ１） Ｆｉｂｏｍｃｃｉ墟 前向星 投都为正的圈 所有圈 所有罔．较常用于先仝ｌ｜ｌ 所有圈．较常闭于稀琉圈 ｏｔ １ ０［ｖ’） 前向星 邻接矩阵 ①给图Ｇ，加一个新结点口ｏ。对％用Ｂｅｌｌｍａｎ－Ｆｏｒｄ，若有负 圈，则结束；否则可以得到／，４ｖ），即 到口的最短路长。ＯｆｒＥ） ０ｑＰｆｂＩＩＶｌ￣ＩＰｌ￡Ｉ Ｆｉｂｏｎａｃｃｉ堆 前向星 ②对于所有边 口Ｊ，权值改造，即令埘，（ 口Ｊ＝埘 口Ｊ ｆｕＪ—ｈ ＯＯｎ） ③对于每个结点，用一次以Ｆｉｂｏｎａｃｃｉ Ｈｅａｐ为优先队列的 Ｄ／ｊｋｓｔｒａ算法．可求出口与其他顶点的最短路。Ｏ（ＶｌｏｇＶ＋Ｅ）＊ｏｆｆ） 。权值改造满足两个原则：（１）Ｗ 非负；（２）对于任意顶点Ｕ，ｖ， Ｐ是在Ｗ上的ｕ到ｖ的最短路当且仅当Ｐ是在Ｗ 上的Ｕ到ｖ 的最短路。下证Ｉｌ『和 埘 口 危ｆｕ卜危 ，满足以上两个原则： （１）由于ｈ是ｖｏ到ｖ的最短路长，危ｒｕＪ＋ｌｃ， 口Ｊ≥危 Ｊ，所以埘 在单源最短路径问题中．Ｄｉｊｋｓｔｒａ算法适合于处理权值都为 正的图．而Ｂｅｌｌｍａｎ则适用于含有负权的图．并且可以处理负权 圈。改进后的ＳＰＦＡ是最快的。 在有向无环图中有特殊的算法，可以在的时问内实现。 在所有点之问的最短路径问题中．我们可以多次运行ＳＰＦＡ 算法。但在完全图中ｎ０ｙｄ算法则更为优秀，并且实现简单。 参考文献： １．Ｈｅｒｂｅｒｔ Ｓ．ＷｉｌＥ．Ａｌｇｏｒｉｔｈｍｓ ａｎｄ Ｃｏｍｐｌｅｘｉｔｙ．Ｕｎｉｖｅｒｓｉｙ ｏｆ ｔＰｅｎｎｓｙｌｖａｎｉａ， １９９４ 砂 口 危（Ｉ ｝－ ≥０。 令路径ｐ＝ 口 Ｌ，ｖＯ，则 ｋ ｋ ２．１１１ｏｍａ￥Ｈ．Ｃｏｒｍｅｎ，Ｃｈａｒｌｅｓ Ｅ．Ｌｅｉｓｅｒｓｏｎ，Ｒ．ｏｎａｌｄ Ｌ．Ｒｉｖｅｓｔ，ａｎｄ Ｃｌｉ髓ｒｄ Ｓｔｅｉｎ．Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔＯ Ａｌｇｏｒｉｔｈｍｓ．ＭＩＴ Ｐｒｅｓｓ，Ｃａｍ ｂｎａｇｅ，ＭＡ，２００１ ３．Ｍｉｃｈａｄ Ｓｉｐｓｃｒ．Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔＯ ｔｈｅ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎ。ｓｅｃｏｎｄ ｅｄｉ＿ ｔｉｏｎ．Ｔｈｏｒｎ∞ｎ，ＵＳＡ，２ｏ０６． １．，ｌ（ｐ）－－Ｚ１．，’（ｙ『＿Ｉ，ｙｆ）＝∑［１．，（ 一Ｉ， ）＋ （ Ｉ）一 （ ）】 ２ ／＝２ ＝１．，（ｐ）＋ （ｙ１）一 （ ） Ｉｌ『例只与ｔ‘Ｉ 以及首尾的标号ｈ有关，不影响Ｉｌ『 Ｊ的决策。所以 Ｉｌ『 上是最短路长当且仅当埘 最短路长，且不影响最短路Ｐ。 ６．结论 ４．Ｒ．ｏｂｅｒｔ Ｓｅｄｇｅｗｉｃｋ，Ｐｈｉｌｉｐｐｅ Ｆｌａｊｏｌｅｔ Ａｎ Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔＯ ｔｈｅ Ａ『ｌ ｙ ｏｆ ＡＩｇｏｒｉｔｈｍｓ．Ａｄｄｉｓｏｎ—Ｗｅｓｌｅｙ Ｐｒｏｆｅｓｓｉｏｎａｌ，ＵＳＡ，２００６．
