交通建模中的最短路径算法分析与测试
任 刚，张 永，周竹萍
（东南大学江苏省交通规划与管理重点实验室，南京 210096）
摘 要：交通建模一直以来就是最短路径算法极为重要的应用领域。介绍主流的最短路径算法——标号算法，
通过交通网络特征分析和实际城市道路网络中的算法测试，给出如何选择适合交通网络的一般最短路径算法的
建议。分析交通建模中各类特殊最短路径算法的研究需求，包括带转向约束的算法，带时窗约束的算法，动态、
随机、自适应算法，k-最短路径算法，启发式搜索算法，再优化算法等。最后对未来研究趋势作出展望。
关键词：交通运输规划与管理；交通建模；最短路径算法；分析与测试
中图分类号：U491 文献标识码：A 文章编号：1673－7180(2009)10－0708－6
Analysis and testing of shortest path algorithms
in transportation modeling
Ren Gang，Zhang Yong，Zhou Zhuping
(Jiangsu Provincial Key Laboratory of Transportation Planning and Management, Southeast University,
Nanjing 210096, China)
Abstract: Transportation modeling is an important application field of shortest path (SP) algorithms. In this paper, labeling
algorithms are introduced. Some suggestions on selecting the general SP algorithms suitable for realistic transportation
networks are proposed according to analysis of transportation network characteristics and to experimental results over
realistic road networks. Some special cases of SP algorithms in transportation modeling, including algorithms with turning
constraints, algorithms with time-window constraints, dynamic, stochastic and adaptive algorithms, k-shortest path algorithms,
heuristic search algorithms, and reoptimization algorithms, are reviewed. Future researches are prospected at last.
Key words: transportation planning and management；transportation modeling；shortest path algorithms；analysis
and testing
0 引 言
自20世纪50年代以来，经典的图论与不断发展完
善的计算机数据结构及算法的有效结合使得各种最短
路径算法不断涌现[1-3]。交通建模一直以来就是最短路径
研究成果极为重要的应用领域，其应用内涵包括2部分：
①一般的最短路径算法在交通建模中的直接应用；②针
对交通建模的特殊要求设计和应用一些特殊类型的算
基金项目：高等学校博士学科点专项科研基金([1**********])；住房和城乡建设部科学技术项目(2008-K5-11)；东南大学优秀青年
教师教学科研资助计划
作者简介：任刚(1976－ )，男，研究员，rengang@seu.edu.cn
中国科技论文在线 Sciencepaper Online 第4卷 第10期
2009年10月
709
法（如带转向约束的最短路径问题等）。这两部分彼此
联系，前者是基础，解决的是交通网络区别于一般抽象
网络的共性问题；后者是拓展，解决的是交通网络针对
不同特殊需要的个性问题。本文在介绍主流的标号算法
基础上，对交通网络中一般最短路径算法的效率进行测
试、比较并给出算法选取建议，回顾交通建模中各类特
殊最短路径算法的研究进展，最后对未来研究情况作一
展望。
1 最短路径算法的主流技术——标号算法
根据路径源点和终点的数目，最短路径问题可分为
单源单汇、单源多汇、多源多汇等类型，其核心是单源
多汇问题。求解最短路径问题的大部分算法都基于如下
事实：网络中从某个源点到其余所有节点的最短路径
集，构成该网络以源点为根的生成树即最短路径树。主
流的最短路径算法是标号算法，核心思想是通过节点扫
描不断更新生成树和节点标号最终获得最短路径树。
根据节点选取策略的不同，标号算法又可以分为标
号设定和标号修正2类。标号设定算法基于最短优先搜
索，当弧长非负时每一步都能得到一条从源点到当前扫
描节点的最短路径，由此若仅需要单源单汇最短路径，
则一旦终点被扫描即可结束。而标号修正算法是基于列
表搜索，算法不管弧长的正负，即使单源单汇问题也需
等到算法完全结束时才能得到。
常用的标号技术包括数据结构、节点存取策略和生
成树更新技术等。数据结构中，一类是适合于标号设定
算法的各种优先队列，如堆、桶以及组合结构，另一类
是适合于标号修正算法的各种列表，如队列、栈、门限
以及组合结构deque等。除了由数据结构本身决定的存
取策略之外，用以提高算法效率的辅助存取策略还包括
阈值设置、拓扑排序等。生成树更新技术（包括标号更
新）通过子树分解关系，将标号更新范围扩展到相应子
树中的所有节点，而不局限于当前的扫描节点。已知的
标号算法均可以视为一个统一的原型算法基于各种标
号技术的不同实现形式，这有助于更好地理解所有标号
算法之间的联系和差异，并拓展出更多有效算法。表1
列出了主要标号算法的相关信息。
表 1 主要的标号算法一览表
Table 1 The major labeling algorithms
分类 算法名称 主要结构和技术 时间复杂度 备注
Dijkstra 无序列表 O(n2
)
S-heap 二叉堆 O(mlogn)
S-heap-F Fibonacci 堆 O(m+nlogn)
非负弧长
S-heap-R1 单层基数堆 O(m+nlogC*
)
S-heap-R2 双层基数堆 O(m+nlogC*
/loglogC*
)
S-heap-R3 基数堆＋Fibonacci堆 Om n C ( log ) ∗ +
S-bucket 桶 O(m+nC*
)
S-bucket-M 限制桶的个数 O(m+n(C*
/B+B))
标号设定算法
S-bucket-D 双桶 O(m+n(C*
/Δ+Δ))
L-bucket-A 近似桶 O(mΔ+n(C*
/Δ+Δ))
非负整数弧长
L-queue 队列 O(nm)
L-deque 队列＋栈 O(n2n
)
L-2queue 双队列 O(n2
m)
L-threshold 队列＋阀值指针 O(nm)
Topological Ordering 队列＋拓扑排序 O(nm)
标号修正算法
SLF 队列＋首元素比较 O(nm)
任意弧长
注：m为弧数，n为节点数，C*
为最大弧长，B为桶数，Δ 为桶间距，时间复杂度在备注要求 的情况下取得。
交通建模中的最短路径算法分析与测试 第4卷 第10期
2009年10月
710 中国科技论文在线 Sciencepaper Online
2 一般最短路径算法在交通网络中的适应性
测试
2.1 交通网络的特征及其表示法
选择适合交通网络的最短路径算法，首先必须分析
交通网络的特征并且设计高效率的交通网络表示法。实
际的交通网络自有不同于一般网络的具体特点：
1) 交通网络由弧数和节点数之比 m/n 决定的平均
邻接度比较低，一般在3左右，属于稀疏网络。一个有
趣的现象是国内城市道路网络的平均邻接度较高，达
3.3 左右，而国外城市则通常在 3 以下[4]。究其原因在
于，国外发达城市的交通管理措施（如路段单向通行、
机动车禁行等）比较完善，使得实际弧数有所降低。
2) 交通网络的弧长一般非负，虽然弧长的实际含
义不一定是路段长度，但即使是广义的弧长（比如费用、
行程时间等）通常也与路段长度呈近似正比关系，因此
弧长分布范围比较均匀。
3) 交通网络结构比较规则，接近于平面图，但是
又可能存在一定的复杂性，比如在同一城市路网中，市
区道路密集，郊区道路就相对稀疏。
对于网络的存储和表示，通常有邻接矩阵、邻接表、
邻接多重表和十字链表等。邻接矩阵由于其空间复杂度
高（一般为 O(n2
)）和关联节点查询速度慢（一般为
O(n)），对于动辄具有成千上万节点的稀疏交通网络很
不适合。邻接多重表和十字链表由于结构和操作比较复
杂，在实践中的应用也仅限于某些专有领域。邻接表是
另一种存储网络拓扑的数据结构，它是一种链式存储结
构，其空间复杂度是 O(m+n)，对于路径分析中关键的
操作——关联节点的查询是O(m/n)，已被证明是网络表
达中最为有效的结构。因此，对于交通网络这样的大型
稀疏图应用邻接表（包括其特殊形式星形表）来存贮数
据已经成为业界的共识[3]。
2.2 实际城市道路网络中的算法测试
针对缺乏在实际城市（尤其是国内城市）道路网络
环境下最短路径算法测试的情况，最近我们将
Cherkassky等[2]在Unix环境下开发且已为业内所认可的
最短路径算法C语言代码适当修改后，移植到一台装有
Windows XP操作系统和Unix模拟环境软件Cygwin、
具有256M内存的Pentium 4计算机上，设计了具有可
比性的测试环境和测试方案，选用了国内外7个真实的
城市道路网络数据对表1中的14种算法进行了测试。
测试用的网络包括镇江、郑州、鞍山和昆山等4个
国内城市路网以及美国芝加哥(Chicago)、西班牙巴塞罗
那(Barcelona)和加拿大温尼伯(Winnipeg)等 3 个国外城
市路网。网络数据取自作者所在实验室以及国外开放数
据网站[5]。各个网络特征如表2所示。
表 2 测试网络特征
Table 2 Properties of tested networks
城市路网 节点数 弧数 平均邻接度
（弧数/节点数）
镇江 252 814 3.230
郑州 317 1 076 3.394
鞍山 347 1 178 3.395
昆山 378 1 186 3.138
芝加哥 993 2 950 2.971
巴塞罗那 1 020 2 522 2.473
温尼伯 1 052 2 848 2.707
本次算法测试的指标以计算速度为主，适当考虑稳
定性。计算速度以查找最短路径树所需的运算时间（不
包括数据录入和结果输出时间）为评价标准，时间越小
则速度越快；稳定性以一定样本群中的上述运算时间的
标准差为评价标准，标准差越高说明这个算法针对某些
源点时要花更多的时间，因此稳定性越差。测试过程中，
对每个测试网络随机选出100个源点，分别测定创建各
个最短路径树需要的时间，最后计算这100个时间数据
的平均值与标准差。由于数量级很小，为了保证精确性，
每个最短路径树的运算时间以重复1 000次并求平均值
的方法获取。
测试结果如表 3 所示，时间数据的单位为 ms。最
后一行给出对应网络中最快算法的运算时间。其他各行
数据对应各个算法，并按算法在测试网络上所表现出来
的总体的计算速度排序（见黑字体列）。其中，“分网络
性能”栏下列出该算法在各个网络中相对于最快算法的
运算时间比，即运算时间与最快算法时间的比率；“总
体性能”栏下显示该算法在所有网络中的运算时间的总
和、运算时间标准差的平均值以及相对于总体最快算法
总运算时间的比率。例如：SLF算法是郑州路网上的最
快算法，计算每个最短路径树的平均时间为 0.40 ms；
S-bucket 则是该网络上的最慢算法，平均运算时间是
SLF 算法的 7.45 倍。而综合各个网络上的表现，
L-2queue算法是总体最快算法，S-heap-F则是总体最慢
算法，总运算时间是L-2queue算法的4.21 倍。 第4卷 第10期 2009年10月
711
表 3 测试结果
Table 3 Testing results
ms
分网络性能 总体性能 算法
镇江 郑州 鞍山 昆山 芝加哥 巴塞罗那 温伯尼 总时间 比率 平均标准差 L-2queue 1.19 1.05 1.00 1.02 1.00 1.02 1.27 6.36 1.00 2.12
L-deque 1.24 1.13 1.04 1.10 1.04 1.00 1.20 6.39 1.00 1.99
SLF 1.00 1.00 1.08 1.00 1.12 1.31 1.80 7.64 1.20 2.81
L-threshold 2.03 2.00 1.57 1.43 1.55 1.08 1.00 7.85 1.23 0.85
L-bucket-A 2.57 2.95 2.08 2.02 1.37 1.36 1.00 9.14 1.44 1.15
S-bucket-D 2.03 2.50 2.19 2.08 1.55 1.54 1.10 9.42 1.48 0.68
L-queue 1.16 1.18 1.25 1.35 1.55 1.56 2.24 9.56 1.50 3.96
S-bucket-M 3.35 4.53 3.32 3.80 1.46 1.37 1.02 11.94 1.88 1.03
Topological
Ordering
2.78 2.70 2.64 2.47 2.72 2.25 2.04 13.93 2.19 5.05
S-heap 2.38 3.15 2.70 2.57 3.39 2.30 2.02 14.83 2.33 1.34
S-heap-R1 4.38 5.33 4.53 4.35 2.41 2.06 1.51 16.25 2.56 0.80
S-bucket 6.41 7.45 6.77 8.12 1.39 1.39 1.01 18.58 2.92 2.34
Dijkstra 1.95 2.85 2.32 2.25 2.83 6.44 3.65 20.71 3.26 2.15
S-heap-F 4.16 5.43 4.66 4.47 5.45 4.94 3.81 26.77 4.21 1.21
最小时间 0.37 0.40 0.53 0.60 1.14 1.08 1.67 5.79
就单源多汇问题而言，上述测试结果表明：①标号
修正算法总体上优于标号设定算法，L-2queue，L-deque，
SLF和L-threshold算法尤为出色；而在标号设定算法内
部，基于桶结构的算法又要好于基于堆结构的算法。②
L-2queue，L-deque 算法的运算时间基本都保持在所在
网络中最快算法的1.2 倍以下，对各种网络的适应性最
好。③SLF 算法更适合平均邻接度较高（如大于 3.2）
的网络，但稳定性有所欠缺（平均标准差达2.81 ms）。
④与此相反，L-threshold算法更适合平均邻接度较低（如
小于 3.0）的网络，并且有很好的稳定性。至于其他类
型问题测试以及更详尽的分析结论可参阅文献[4]。
3 交通建模中特殊类型的最短路径算法分析
多样化的交通建模对最短路径问题设置了更多的
约束条件，由此衍生出不少应用于但不局限于交通领域
的特殊类型的最短路径算法，包括带转向约束的算法，
带时窗约束的算法，动态、随机、自适应算法，k-最短
路径算法，启发式搜索算法，再优化算法等。
3.1 带转向约束的算法
交通建模中经常需要求解转向约束下的最短路径
问题，例如考虑交叉口的转向延误和转向禁行、考虑不
同出行方式间的换乘费用。普通的算法对此无能为力，
解决问题的途径有2条：①间接法——通过变换网络形
式将转向约束直接体现在网络结构中，然后用普通算法
求解，包括对偶网络法、扩展网络法等；②直接法——
从算法本身入手直接求解问题，包括Vine-building算法、 弧标号算法、节点标号算法等。其中，Vine-building算
法和扩展网络法存在明显缺陷，其余3种方法更为有效。 任刚等全面分析了此类问题[6-8]，提出对偶最短路径
树(DSPT)概念并利用其在现有方法中建立联系，使得将
普通最短路径算法成果借用于此类问题中成为可能。
3.2 动态、随机和自适应算法
与普通（静态）最短路径问题相比，动态最短路径
问题中的路段权重、节点延误等均为时间的函数，这更
符合城市交通网络的时变特征。在假定路径长度服从先
入先出(FIFO)原则的前提下，任何静态标号算法均可以
交通建模中的最短路径算法分析与测试 第4卷 第10期 2009年10月
712 中国科技论文在线 Sciencepaper Online
扩展为动态最短路径算法[9]。
由于城市交通网络充满不确定因素，路段权重不再
是一个常数而是一个满足某种概率分布函数的随机变
量，由此异于普通（确定）最短路径问题的随机问题应
运而生。在此类问题中，求解期望最短路径比求解可能
最短路径更具实用意义。幸运地是，若用路段的期望权
重替代随机权重，期望最短路径可用普通最短路径算法
求解。当路段权重既是动态的又是随机的，问题变得更
为复杂。
上述算法中，一旦路段权重的概率密度时变函数已
知，某个起终点之间的期望最短路径在出行者离开起点
前就能确定下来，即这样得到的期望最短路径是先验
的、非自适应的。而在ITS环境中，出行者在出行途中
可以接收到关于前方路段的最新信息，并结合已经历路
段的实际情况，不断调整自己的决策、找出从当前位置
通向目的地的最短路径，这就是自适应的动态随机最短
路径搜索过程。
3.3 带时窗约束的算法
时窗(time window)是最普遍的时间约束形式，即网
络节点只能在特定时间段内被访问，城市道路交叉口信
号配时即可视为一个循环的时窗序列。时窗约束分2类： 硬时窗和软时窗。在硬时窗约束下，算法目标是找到从
源点到终点的最小费用路径使得所有中间节点能在各
自的时窗内被访问。在软时窗约束下，路径费用最小依
然是优化目标，但是一旦违例（即访问中间节点的时间
超过了这些节点的时窗范围），则需要额外附加与违例
次数相关的惩罚费用。
3.4 k-最短路径算法
在许多情况下不仅仅要考虑最短路也要考虑次短
路、次次短路等，即k-最短路径问题。比如，为增大用
户的选择余地，路径诱导系统通常要为用户提供几条可
行的路径（包括最短路径），以便用户根据自己的习惯
和喜好进行选择，也适合于当最短路径不可行时选择更
为现实的同时也是较好的代用方案。k-最短路径算法可
以同时求出长度从小到大排列的k条最短路径，有2种
解决思路[10]：①递推法——在最短路径（称为第一最短
路径）的基础上，求解一条次最短路径（称为第二最短
路径），重复此过程k－1次，就可得到k条最短路径；
②直接法——直接求出k条最短路径。
3.5 启发式搜索算法
面对路网交通瞬息万变的运行状态，最短路径算法
的时效性在诸如实时路径诱导系统等应用场合中是首
要的。对此，除了采用对硬件要求较高的并行计算策略
外，可以考虑采用启发式搜索策略“以精度换速度”。
启发式搜索是一种尽可能基于现有信息的搜索策略，
即在搜索过程中尽量利用目前已知的诸如迭代步数
以及从初始状态和当前状态到目标状态估计所需要
的费用等信息，通常采用限制搜索范围、分解搜索目
标等策略[11]。目前最流行的启发式搜索算法当属由Hart
等首先提出的A*算法[12]。
3.6 再优化算法
在交通建模中（例如均衡交通分配）经常会有如下
需要：多次甚至不断地搜索最短路径树，但相邻2次搜
索的条件和要求差别不大，要么是源点改变而网络中所
有弧的长度保持不变，要么是源点不变而网络中部分弧
的长度发生了改变（增加或减少）。尽管这可以通过 2
次独立的、完整的最短路径算法调用来实现，但是另一
种做法对于大型网络而言通常更节省计算时间[1]，即：
采用一定的再优化(reoptimization)技术，更新前一次得
到的最短路径树，获得源点或弧长改变后的新的最短路
径树，这就是最短路径再优化算法的基本思路。此类算
法多借助于对偶算法技术、图及其生成树的分解技术。
4 研究 展望
由国内外研究现状及其应用需求可见，未来关于交
通建模中最短路径问题的研究除了进一步分析各种普
通的最短路径算法在交通网络中的实际性能以外，面向
交通建模尤其ITS应用领域的各种特殊问题类型将是研
究热点和重点，并且在总体上呈现出3大趋势：
1) 约束条件的多样性。异于一般的最短路径搜索，
从路径形式、路权准则和网络状态等方面设置更多的约
束条件，例如：最短路径必须经过某些节点或某些弧，
满足各种交通管理与控制措施的限制条件，路权中考虑
时间和成本双准则，路权信息动态、随机且自适应等。
2) 算法效率的实时性。实时路径诱导系统等现代
交通科技的发展和实施对最短路径算法研究提出了新
的挑战——在约束条件日趋多样、问题结构日益复杂的
同时对算法实时性的要求却更为苛刻[13]，包括启发式搜
索、再优化策略特别是并行计算均是实时性要求的产
物。针对串行计算机的最短路径算法几乎已达到理论上
的时间复杂度极限[14]，基于图分解的并行算法将成为一
个主要研究方向。
3) 算法设计的针对性。最短路径算法研究的切入
点应由寻求普遍适用的“最佳算法”转移到寻求面向
问题的“特定算法”上，也就是抓住所要解决的交通
建模问题的特征，设计适合问题的特定数据结构、运
行结构与搜索策略，尽可能提高算法在实际问题上的
时空效率。 第4卷 第10期
2009年10月
713
[参考文献](References)
[1] Pallottino S, Scutella M G. Shortest path algorithms in transportation models: classical and innovative aspects. [C]// Marcotte P, Nguyen S, eds. Equilibrium and Advanced Transportation Modeling. Boston: Kluwer, 1998: 245-281.
[2] Cherkassky B V, Goldberg A V, Radzik T. Shortest paths
algorithms: theory and experimental evaluation (Technical report 94-1480) [R]. California: Computer Science Department, Stanford University, 1993.
[3] 陆锋. 最短路径算法: 分类体系与研究进展[J]. 测绘学报, 2001, 30(3): 269-275.
Lu Feng. Shortest path algorithms: taxonomy and advance in research [J]. Acta Geodaetica Et Cartographic Sinica, 2001, 30(3): 269-275. (in Chinese)
[4] 李岩. 城市交通网络中最优路径算法的比较分析[D]. 南京：东 南大学交通学院，2006.
Li Yan. Comparison and analysis of optimal path algorithm in urban transportation network [D]. Nanjing: School of Transportation, Southeast University, 2006. (in Chinese)
[5] Transportation Network Test Problems [EB/OL].
http://www.bgu.ac.il/~bargera/tntp/
[6] 任刚，王炜，邓卫. 带转向延误和限制的最短路径问题及其求 解方法[J]. 东南大学学报: 自然科学版, 2004, 34(1): 104-108.
Ren Gang, Wang Wei, Deng Wei. Shortest path problem with turn penalties and prohibitions and its solutions [J]. Journal of Southeast University: Natural Science Edition, 2004, 34(1): 104-108. (in Chinese)
[7] 任刚. 交通管理措施下的交通分配模型与算法[M]. 南京：东南 大学出版社，2007.
Ren Gang. Traffic assignment models and algorithms with traffic management [M]. Nanjing: Southeast University Press, 2007. (in Chinese)
[8] 任刚，王炜. 转向约束网络中的对偶最短路径树原理及其原型 算法[J]. 交通运输工程学报, 2008, 8(4): 84-89.
Ren Gang, Wang Wei. Principles and its prototype algorithm for dual shortest path tree in networks with turning constraints [J]. Journal of Traffic and Transportation Engineering, 2008, 8(4): 84-89. (in Chinese)
[9] Subramanian S. Routing algorithms for dynamic, intelligent transportation networks [D]. Virginia: Virginia Polytechnic Institute and State University, 1997.
[10] 张可. 车辆导航系统关键技术研究[D]. 北京：北京工业大学， 2001.
Zhang Ke. Research on key technologies of vehicle navigation system [D]. Beijing: Beijing University of Technology, 2001. (in Chinese)
[11] Fu L, Sun D, Rilett L R. Heuristic shortest path algorithms for transportation applications: State of the art [J]. Computers & Operations Research, 2006, 33(11): 3324-3343.
[12] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transaction on System Science and Cybernetics, 1968, 4(2):100-107.
[13] 李威武, 王慧, 钱积新. 智能交通系统中路径诱导算法研究进 展[J]. 浙江大学学报: 工学版, 2005, 39(6): 819-825.
Li Weiwu, Wang Hui, Qian Jixin. New trends in route guidance algorithm research of intelligent transportation system [J]. Journal of Zhejiang University: Engineering Science , 2005, 39(6):
819-825. (in Chinese)
[14] 倪安宁, 隽志才, 高林杰. 交通网络最短路径并行算法研究综 述[J]. 公路交通科技, 2006, 23(12): 128-132.
Ni Anning, Juan Zhicai, Gao Linjie. An overview of research on
parallel shortest path algorithm in transportation network [J]. Journal of Highway and Transportation Research and Development, 2006, 23(12): 128-132. (in Chinese)