浅析城市道路网中的最短路径算法

优先搜索、深度优先搜索、代价树的广度优先搜索以
及代价树的深度优先搜索都属于盲目搜索策略。而
启发式搜索的特点是在搜索中加入了与问wenku.baidu.com有关的
启发性信息，这些信息可以指导搜索朝着问题希望
的方向发展。
Ａ＊ 算法在人工智能中是一个典型的启发式搜
索算法。Ａ＊ 算法也是一种最好优先搜索算法，只不过
要加上一些约束条件。Ａ＊ 算法的估价函数表示为［４］：
第 ７ 卷第 １ 期 ２００８ 年 ３ 月
长沙通信职业技术学院学报
长沙通信职业技术学院学报 Ｊｏｕｒｎａｌ ｏｆ Ｃｈａｎｇｓｈａ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ
ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｖｏｃａｔｉｏｎａｌ Ｃｏｌｌｅｇｅ
第７卷
Ｖｏｌ．７ Ｎｏ．１ Ｍａｒ．２００８
浅析城市道路网中的最短路径算法
因此，针对城市道路网进行最短路径分析的研 究不仅可以解决实际应用系统的需求，而且可以很 方便地将其研究成果推广到一般的道路网上面。
１ 经典最短路径算法分析
由于最短路径问题特征、网络特性等的纷繁复 杂，最短路径算法表现出多样性。总的来说，最短路
径算法可通过对问题类型、网络特征和求解技术的 不同来进行分类。下面重点分析三类经典最短路径 算法：
（ Ｃｈａｎｇｓｈａ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｖｏｃａｔｉｏｎａｌ Ｃｏｌｌｅｇｅ， Ｃｈａｎｇｓｈａ， Ｈｕ＇ｎａｎ， Ｃｈｉｎａ ４１００１５）
Ａｂｓｔｒ ａｃｔ： Ｔｈｉｓ ｐａｐｅｒ ｍａｉｎｌｙ ａｎａｌｙｚｅｓ ｓｏｍｅ ｃｌａｓｓｉｃａｌ ｓｈｏｒｔｅｓｔ ｐａｔｈ ａｌｇｏｒｉｔｈｍｓ ａｎｄ ｔｈｅｉｒ ｒｅｓｐｅｃｔｉｖｅ ｌｉｍｉｔａｔｉｏｎｓ ｗｈｅｎ ｕｓｅｄ ｓｅｐａｒａｔｅｌｙ ｉｎ ｔｈｅ ｕｒｂａｎ ｒｏａｄ ｎｅｔｗｏｒｋ． Ｔｈｅｎ， ｉｔ ｐｕｔｓ ｆｏｒｗａｒｄ ａｎ ｉｍｐｒｏｖｅｄ Ｄｉｊｋｓｔｒａ ａｌｇｏｒｉｔｈｍ ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ａｎｄ ｅｘｐｏｕｎｄｓ ｉｔｓ ａｄｖａｎｔａｇｅｓ ｏｖｅｒ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ａｌｇｏｒｉｔｈｍｓ．
Ｇ＝（Ｖ， Ｅ， ｆ） Ｖ＝｛ ｖ１，ｖ２，ｖ３，ｖ４，ｖ５｝ Ｖｉ＝（ＸＶｉ，ＹＶｉ） ｉ＝１，２，３，４，Λ Ｅ＝｛ｅ１，ｅ２，ｅ３，ｅ４，ｅ５，ｅ６，ｅ７，ｅ８｝ ｆ： ｆ（ｅ１）＝ｆ（ｖ１，ｖ２） ｆ（ｅ２）＝ｆ（ｖ２，ｖ３） ｆ（ｅ３）＝ｆ（ｖ１，ｖ５） ｆ（ｅ４）＝ｆ（ｖ３，ｖ４） ｆ（ｅ５）＝ｆ（ｖ２，ｖ４） ｆ（ｅ６）＝ｆ（ｖ４，ｖ５） ｆ（ｅ７）＝ｆ（ｖ１，ｖ３） ｆ（ｅ８）＝ｆ（ｖ２，ｖ５） 下面分析一下传统 Ｄｉｊｋｓｔｒａ 的基本原理 ［１］：首 先，引进一个辅助向量 ｄ（ｕ，ｖ），它的每个分量 ｄ（ｕ，ｖ） 表示当前找到的从起点 ｕ 到终点 ｖ 的最短路径长 度。在算法过程中 ｄ（ｕ，ｖ）的值是在不断逼近最终结 果但在过程中不一定就等于最短路径长度。它的初 始状态为：若从 ｕ 到 ｖｉ 有弧，则 ｄ（ｕ， ｖｉ ）为弧上的权 值；否则置 ｄ（ｕ， ｖｉ ）为 ∞，显然，长度为 ｄ（ｕ， ｖｊ ）＝ Ｍｉｎ ｛ｄ（ｕ，ｖｉ） ｖｉ∈Ｖ｝的路径就是从 ｖ 出发的长度最短的一 条最短路径，此路径为 （ｕ， ｖｊ ）。 那么，下一条长度次短的最短路径是哪一条呢？ 假设该次短路径的终点是 ｖｋ，则可想而知，这条路径 或者是 （ｖ， ｖｋ ），或者是 （ｖ， ｖｊ ，ｖｋ）。它的长度或者是从 ｖ 到 ｖｋ 的弧上的权值，或者是 ｄ（ｕ， ｖｊ ）和从 ｖｊ 到 ｖｋ 的弧的权值之和。 一般情况下，假设 Ｓ 为已求得最短路径的终点 的集合，则可证明：下一条最短路径（设其终点为 Ｘ） 或者是弧（ｖ，ｘ），或者是中间只经过 Ｓ 集合中的顶点 而最后到达顶点 Ｘ 的路径。因此，下一条长度次短 的最短路径长度必是 Ｄ［ｊ］ ＝ Ｍｉｎ｛Ｄ［ｉ］ ｖｉ ∈Ｖ－ Ｓ｝。其 中，Ｄ［ｉ］或者是弧 （ｖ， ｖｉ ）上的权值，或者是 Ｄ［ｋ］（ ｖｋ ∈
１）传统的 Ｄｉｊｋｓｔｒａ 算法 传统的 Ｄｉｊｋｓｔｒａ 算法是求解最短路径问题的经 典算法，Ｄｉｊｋｓｔｒａ 算法是建立在抽象的网络模型上， 把路线抽象为网络中的边，以边的权值来表示道路 的相关的参数，算法确定了赋权网络中从某点到所 有其它节点的具有最小权值的路径，Ｄｉｊｋｓｔｒａ 算法是 求解最小权问题的通用算法，它忽略了网络模型的 个体特性，因此它的算法复杂度较高，在城市道路网 的路径寻优问题中，网络模型具有如下特点：网络模 型中的顶点数多，一般顶点数多达上千或上万；对网 络模型中的路线查询一般需要一定的动态性。 因此，虽然传统 Ｄｉｊｋｓｔｒａ 算法理论上是可行的， 但是考虑到计算机硬件水平等其它限制，如果直接
大的。
３）启发式搜索（Ｈｅｕｒｉｓｔｉｃ Ｓｅａｒｃｈ）算法——Ａ＊ 算
法
搜索是人工智能中的一个基本问题，搜索可分
为盲目搜索和启发式搜索。盲目搜索的特点是按预
定的控制策略在搜索过程中获得中间信息，不用来
改变控制策略。由于搜索总是按照预先规定的路线
来进行，没有考虑问题本身的特性，所以这种搜索具
有盲目性，效率不高，不便于复杂问题的求解。广度
陈献辉 （ 长沙通信职业技术学院， 湖南长沙 ４１００１５ ）
【摘 要】 论文主要分析了一些经典的最短路径算法，以及这些最短路径算法单独应用于城市道路网中存在的局限性。
在此基础上提出了一种改进的 Ｄｉｊｋｓｔｒａ 算法用来解决城市道路网中的最短路径问题，并给出了改进后的算法优于传统算法的
优势之处。
【关 键 词】道路网；最短路径；算法；优化
ｆ ＊ （ｊ）＝ ｇ（ｊ）＋ｈ＊ （ｊ）
（３．３）
其中 ｇ （ｊ）是从起点到当前节点 ｊ 的实际代价的
度量，ｈ ＊ （ｊ）是从当前节点 ｊ 到终点的最佳代价的
估计。我们注意到若 ｈ ＊ （ｊ）＝０ 即没有任何全局信
息，这里的 Ａ＊ 算法就变成了经典 Ｄｉｊｋｓｔｒａ 算法。这
也就说明了 Ｄｉｊｋｓｔｒａ 算法是 Ａ＊ 算法的特殊情况。
Ｋｅｙ ｗｏｒ ｄｓ： ｒｏａｄ ｎｅｔｗｏｒｋ； ｓｈｏｒｔｅｓｔ ｐａｔｈ； ａｌｇｏｒｉｔｈｍ； ｏｐｔｉｍｉｚａｔｉｏｎ
最短路径算法在各种城市应急系统 （如 １１０ 匪 警、１１９ 火警和 １２０ 急救系统）的应用非常广泛。城 市道路网除具有一般道路网的特点之外，还有其特 殊之处。主要表现在：数据量大。对于大型城市来说， 城市道路网中的路段数往往动辄成千上万计， 结构 复杂。随着城市规模的发展，城市交通系统越来越向 复杂的方向发展，多车道、单行线、转弯限制、立交系 统等交通特征变得越来越普遍，加上新的越来越复 杂的交通规则，这些都使得城市道路网的结构变得 复杂。
２） 选择 ｖｊ，使得 ｄ［ｕ， ｖｊ ］＝ Ｍｉｎ｛ｄ［ｕ，ｖｉ］ ｖｉ∈Ｖ－ Ｓ｝． ３） 修改从顶点 ｖｉ ∈Ｓ 出发到集合 Ｖ－ Ｓ 任一顶 点 ｖｋ 可达的最短路径长度，如果 ｄ［ｕ， ｖｊ ］＋ ｆ［ｊ，ｋ］πｄ（ｕ， ｖｋ），则修改 ｄ（ｕ， ｖｋ ）＝ ｄ（ｕ，ｖｊ）＋ｆ［ｊ，ｋ］． ４） 重复操作（２），（３）共 ｎ－ １ 次，由此求得从 ｕ 到 图上其余各顶点的最短路径长度是递增序列，并且 就可以得到最短路径。 Ｄｉｊｋｓｔｒａ 算法最初设计是从一点出发计算到网 络上其它各点的最短路径，所以当应用于道路网的 最优路径计算时，由于已经知道起点和终点，所以可 以改进 Ｄｉｊｋｓｔｒａ 算法，从起点开始搜索，当搜索到终 点，可以停止搜索，就可得到最短路径。 从算法过程中不难发现，Ｄｉｊｋｓｔｒａ 算法虽然适用 的网络类型非常广，但是该算法随着网络的复杂，计 算量也都增加，如果把它直接应用于道路网的最优 路径计算，计算量非常大，而且不能满足动态的要 求。 ２）Ｆｌｏｙｄ 算法 Ｆｌｏｙｄ 算法可以一次求出所有点对点之间的最 短有向路径。它的基本思想是：假设求从定点 ｖｉ 到 ｖｊ 的最短路径。如果从 ｖｉ 到 ｖｊ 有弧，则从 ｖｉ 到 ｖｊ 存 在一条长度为 ａｒｃｓ［ｉ］［ｊ］的路径，该路径不一定是最短 路径，尚需进行 ｎ 次试探。首先考虑路径（ｖｉ ，ｖ０ ，ｖｊ）是 否存在。如果存在，则比较 （ｖｉ ，ｖｊ）和 （ｖｉ ，ｖ０ ，ｖｊ）的路径 的长度取较短者为从 ｖｉ 到 ｖｊ 的顶点序号不大于零 的最短路径。假如在路径上再增添一个顶点 ｖ１，也就 是说，如果 （ｖｉ ，Λｖ１）和 （ｖ１ ，Λｖｊ）分别是当前找到的 顶点的序号不大于零的最短路径。那么 （ｖｉ ，Λ，ｖ１，Λ，ｖｊ） 就有可能是从 ｖｉ 到 ｖｊ 的中间结点不大于 １ 的最短 路径。将它和已经得到的从 ｖｉ 到 ｖ ｊ 中间顶点序号 不大于零的最短路径进行比较，从中选出中间顶点 的序号不大于 １ 的最短路径之后，再增加一个顶点 ｖ２，继续进行试探。依次类推。在一般情况下，若（ｖｉ，Λ， ｖｋ）和 （ｖｋ，Λ，ｖｊ）分别是从 ｖｉ 到 ｖｋ 和从 ｖｋ 到ｖｊ 的序号不 大于 ｋ－ １ 的最短路径，则将（ｖｉ ，Λ，ｖｋ，Λｖｊ）和已经得到 的从 ｖｉ 到 ｖｊ 的中间结点不大于ｋ－ １ 的最短路径相比 较，其长度较短者便是从 ｖｉ 到 ｖｊ 的中间顶点不大于
虽然 Ａ＊ 算法从理论上可以证明适合求解城市
道路网的问题，但是在一般情况下，Ａ＊ 算法是无法
避免指数爆炸的。这是因为很难估计到准确的全局
信息所造成的。在这种情况下，使用 Ａ＊ 算法的算法 复杂度就是无法估计的，也是不可行的。
２ 应用改进的数据结构
在原始的 Ｄｉｊｋｓｔｒａ 算法中，临时标记节点无序 的存储在无序表中，这无疑成为 Ｄｉｊｋｓｔｒａ 算法的瓶 颈。因此每次从临时标记点中搜索路径最短的节点 时都要遍历所有的临时标记节点。解决这个问题的 办法就是将所有的路段权值按照起点和终点分别排 序，每个搜索过程只需较少地遍历临时标记节点。这 也是目前各种基于 Ｄｉｊｋｓｔｒａ 算法的优化算法的重要 出发点之一。另外一个优化途径是尽量减少最短路 径分析过程中搜索的临时节点数量，从而尽快到达 目标节点。
［ 收稿日期］ ２００７－ １２－ ２４ ［ 作者简介］ 陈献辉 （１９７９－），女，湖南长沙人，长沙通信职业技术学院计算机信息工程系教师，硕士，研究方向：数据
库设计、程序设计、数据结构。
４２
第１期
浅析城市道路网中的最短路径算法
使用到实际中，不能满足要求。不过当前的许多流行 的最短路径算法很多还是基于 Ｄｉｊｋｓｔｒａ 算法的，不 同的是都是根据实际的网络拓扑环境的限制条件、 自身特征的因素等进行修改。
Ｓ） 和弧 （ｖｋ ，ｖｉ）上的权值之和。 Ｄｉｊｋｓｔｒａ 算法过程的具体描述如下： １） 如果 （ｕ， ｖｉ ）之间没有直接存在连线，则置 ｆ
［ｕ， ｖｉ ］为 ∞，Ｓ 为已找到从 ｕ 出发的最短路径的终点 的集合，初始状态为空集。那么，从起点 ｕ 到图上其 余各顶点，ｖｉ 可能到达的最短路径长度的初值为 ｄ （ｕ， ｖｉ ）＝ ｆ［ｕ，ｖｉ］，ｖｉ 是与起点邻接的点。
４３
长沙通信职业技术学院学报
第７卷
ｋ 的最短路径。这样，经过 ｎ 次比较后，最后求得的必
是从 ｖｉ 到 ｖｊ 的最短路径［３］。 Ｆｌｏｙｄ 算法应该算是穷举型算法，它在求每一对
顶点之间的最短路径的时候要把网络中的所有具有
连通性的顶点作为中间顶点来运算，对于我们有上
万个顶点的城市道路网来说这个时间复杂度是相当
【中 图 分 类 号】ＴＰ３０１．６
【文 献 标 识 码】Ａ
【文章编号】１６７１－ ９５８１（２００８）－ ０１－ ００４２－ ０５
Ｂｒ ｉｅｆｌｙ ｏｎ ｔｈｅ ｓｈｏｒ ｔｅｓｔ ｐａｔｈ ａｌｇｏｒ ｉｔｈｍ ｉｎ ｔｈｅ ｕｒ ｂａｎ ｒ ｏａｄ ｎｅｔｗｏｒ ｋ
ＣＨＥＮ Ｘｉａｎ－ ｈｕｉ
Ｄｉｊｋｓｔｒａ 算法描述的是算法的实现方法，与网络 的存储结构无关，不同的实现方法决定了不同的时 间复杂度。现实世界的空间实物各式各样，在千变万 化的空间数据中不乏有这样一类空间数据模型，他 们由点－ 线构成空间网络，而且可以用一个坐标系统 来标志空间网络中的各点，网络中的线具有长度的 属性。例如生活中的道路网、管线网、河流网等。这类 空间网络可以表示为矢量化的网络模型 Ｇ，Ｇ 可以 用一个有序三元组（Ｖ，Ｅ，ｆ）表示，其中 Ｖ 是网络模型 Ｇ 的顶点集合，Ｅ 是边集，而 ｆ 是函数，ｆ （ｅ）表示边 ｅ （ ｅ∈ Ｅ）的长度，也就是 Ｇ 中边 ｅ 对应的顶点对（ｕ，ｖ） 之间的距离，因此 ｆ 也可以表示为 ｆ （ｕ，ｖ）。