基于城市道路网的最短路径分析解决方案PDF样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

基于城市道路网的最短路径分析解决方案

刘云翔　陈　荦　李　军　陈宏盛

(国防科技大学电子科学与工程学院, 湖南长沙 410073)

摘　要: 近年来 G IS 对网络分析功能的需求迅速增长. 网络分析中的一个关键问题是最短路径问题, 它作为许多领域

中选择最优问题的基础, 在交通网络分析系统中占有重要地位. 由于最短路径分析常见于汽车导航系统以及各种城市 应急系统(如 110 报警、 119 火警以及 120 急救系统) , 本文针对城市道路网的特点, 提出了一种实用、 高效的最短路径
分析解决方案.

关键词: 最短路径; D ijk st ra 算法; 城市道路网

中图分类号: T P 391. 4 文献标识码: A 文章编号: 1000 1220 ( ) 07 1390 04

An Im p lem en ta t ion of the Shor te st Pa th Ana lys is Ba sed on C ity Road Ne twork

2
,
2

L IU Yun X iang, CH EN L uo , L I J un
CH EN H o ng Sheng

(S chool of E lectron ic S cience and E ng ineering , N a tiona l U n iv ersity
of
D ef ense T echnology , C hang sha 410073, C h ina)

Abstrac t In recen t yea r s, N e tw o rk ana ly se s have becom e m o re and m o re im po r tan t in G IS.
A s the key p ro b lem o f

2
ne tw o rk ana ly se s, com p u t ing sho r te st p a th s o ve r a ne tw o rk ha s becom e an im po r tan t ta sk in m any ne tw o rk and t ran s
po r ta t io n re la ted ana ly se s.
Sho r te st p a th ana ly sis is o f ten u sed in
veh icle nav iga t io n sy stem

2
and city em e rgency sy s
tem s. T h is p ap e r in t ro duce s a p ract ica l and eff icien t rea liza t io n o f sho r te st p a th ana ly sis acco rd ing to
the cha racte r ist ics

2

2
o f city ro ad ne tw o rk. W e run o u r a lgo r ithm o n a m idd le range p e r so na l com p u te r w ith re la t ive ly la rge da ta se t. T he ex

p e r im en ta l re su lt is ve ry p rom ising, thu s p ro ve s the eff iciency o f the p ropo sed a lgo r ithm.
2
2

Key words sho r te st p a th;
d ijk st ra a lgo r ithm s; ro ad ne tw o rk

2

1 引　言

近年来由于普遍使用 G IS 管理大型网状设施(如城市中

的道路网、 各类地下管线、 通讯线路等) , 使得对网络分析功能

的需求迅速增长. 通用的网络分析功能包括路径分析、 资源分

配、 连通分析、 流分析等. 网络分析中最基本的问题是最短路

径问题, 它作为许多领域中选择最优问题的基础, 在交通网络

分析系统中占有重要地位. 从网络模型的角度看, 最短路径分

析就是在指定网络中两结点间找一条阻碍强度最小的路径.

根据阻碍强度的不同定义, 最短路径不但仅指一般地理意义

上的距离最短, 还能够引申到其它的度量, 如时间、 费用、 线路

容量等. 由于最短路径问题在实际中常见于汽车导航系统以

及各种城市应急系统等(如 110 报警、 119 火警以及 120 急救

系统) , 本文对基于城市道路网的最短路径分析进行了深入研

究.

2　实现机制

要对城市道路网进行最短路径分析, 首先必须将现实中

的城市道路网络实体抽象化为网络图论理论中的网络图, 然
后经过图论中的网络分析理论来实现道路网络的最短路径分

析. 在实际应用中, 城市道路网的表现形式一般为数字化的矢

量地图, 其网络空间特征中的交叉路口坐标和道路位置坐标

是在地图上借助图形来识别和解释的; 而为了能够高效率地

进行最短路径分析, 必须首先将其按结点和弧的关系抽象为

图的结构. 这就需要先对原始道路图进行预处理, 建立其相应

的网络拓扑关系. 预处理的工作主要包括:

· 对原始的道路图进行线元素的拓扑检查、 进行剪断处

理, 生成线和线相互不相交叉的道路图;

· 对剪断后的道路图创立拓扑关系, 并定义其属性特

征, 如道路名称、 道路距离、 交通流量等;

· 生成有拓扑关系的拓扑文件.

经过预处理后, 最短路径分析算法直接从拓扑文件中提

取道路网的网络拓扑结构并加载到内存中, 从而提高路径分

析的效率. 如果由于城市建设的快速发展, 城市道路发生了变

化, 地图更新后, 只需重新进行预处理生成拓扑文件. 系统的

整个工作流程见图 1.

要实现这样的系统主要需解决两个关键问题:

(1) 如何用地图表示城市道路网以及提取网络拓扑结构;

　　收稿日期: 208224　作者简介: 刘云翔, 硕士研究生, 主要研究领域为地理信息系统与数据库技术. 李军, 博士, 讲师, 主要研究领域为地

理信息系统与信息可视化技术. 陈宏盛, 硕士, 副教授, 主要研究领域为人工智能与数据库. 陈荦, 硕士, 讲师, 主要研究领域为地理信息系统与 数据库技术.

© 1995- Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

7 期　　　　　　　 刘云翔等: 基于城市道路网的最短路径分析解决方案 　　 1391

　　(2) 如何高效率地进行最短路径分析.

本文将对这两个问题分别提出解决方案.

图 1　系统工作流程

F ig. 1 T he w o rkf low o f sy stem
3　城市道路网的地图表示和网络拓扑结构的提取

G IS 中的矢量地图是按图层组织的, 即将一幅地图分成

多个层层叠加的透明层, 这些透明层就称为图层. 每个图层存

放一类专题或一类信息, 它由点、 线、 面等空间对象的集合组

成. 一般将描述空间对象的数据分为两类, 即空间数据和属性

数据. 其中, 空间数据记录的是空间对象的位置、 拓扑关系和

几何特征; 属性数据是对空间数据的语义描述, 反映了空间对

象的本质特征. 典型的属性数据有空间对象的名称、 类型和对

象特征等. 一般在 G IS 中, 空间数据和属性数据是分别存储

的. 如在M ap Info 中, 属性数据以数据库的形式存储为一张

表, 而空间数据则以M ap Info 自己定义的格式保存于文件之

中. 两者之间经过一定的索引机制联系起来.

针对图层组织的特点, 我们将城市道路网单独作为一个

图层处理, 称之为道路层. 将实际的城市道路网转化到地图的

图层中时, 若将每一条街道(在网络图中对应于每一条弧) 和

街道的交叉路口(在网络图中对应于每一个结点) 都作为地理

对象保存在图层中, 不但会给地图的制作造成很大的工作量,

而且不利于日后地图的维护. 同时, 在最短路径分析时, 用户

往往关心的只是街道的相关信息. 因此我们只将各条街道作

为线对象保存在图层中. 至于街道的属性数据和交叉路口的

坐标信息, 虽然各 G IS 软件对其属性数据文件和空间数据文

件的具体格式是不公开的, 很难从中直接提取. 但它们均提供

了相应的数据交换文件, 以用于空间数据和属性数据的数据

交换. 如M ap Info 的. M IF 和. M ID 文件, A rc Info 的 shap ef ile

文件等. 为了方便起见, 在以下的讨论中, 我们仅针对M ap In2

fo 的文件结构进行讨论.

在M ap Info 中, 每个图层均有其对应的属性数据表结构

文件(. TA B ). 属性数据表结构文件定义了图层中空间对象

的属性数据的表结构, 包括字段数、 字段名称、 字段类型和字

段宽度等, 另外还指出索引字段及一些用于显示的参数设置

等. 因此我们在道路层的属性数据表结构文件中定义街道的

属性信息字段如下:

表 1　街道的属性信息字段

T ab le 1 T he a t t r ibu te f ie ld o f st ree t s

街道 ID 街道名称 正向权值 反向权值

　　其中, 街道 ID 是街道唯一的标识号; 街道名称是街道的

物理名称; 街道的正向、 反向权值是不同方向上街道的权值,

其方向是由地图绘制的方向确定. M ap Info 对地图中的每一

图层能够生成一种交换格式文件, 它将地图空间数据与属性

数据用文字的方式表示了出来. 交换格式文件包含有两类文

件, 其中. M IF 文件主要包含了空间数据, 指明了地图的坐标

系、 属性表结构、 地图对象的类型和地理坐标信息等(其文件

结构如图 2 所示). . M ID 文件则详细描述了各地图对象的属

性信息, 它的记录排列顺序与. M IF 文件中空间对象的排列

顺序一致.

V e r sio n 2

D e lim ite r " , " Index 1, 3

Coo rdSy s Ea r th P ro jiect io n 1, 104 Co lum n s 3

　　S t ree t C ha r (40) 　　T yp e In tege r 　　D a ta

L ine 122. 4677 37. 7866
122.
4675
37.
7847
　　P en
(1, 2, 0)

L ine 122. 4675 37. 7847
122.
4675
37.
7828
　　P en
(1, 2, 0)

L ine 122. 4675 37. 7828
122.
4674
37.
7809
　　P en
(1, 2, 0)

L ine 122. 4767 37. 7809
122.
4673
37.
779
P en
(1, 2, 0)
2

　　2

2

2

2

2

2

2

图 2 M IF 文件结构示例

F ig. 2 A n exam p le o f . M IF f ile st ructu re

从图 2 中能够看出, 在. M IF 文件中对于图层中的每一

个线对象, 均记录了该线对象的起点和终点的经纬度坐标. 因

此我们能够直接对. M IF 文件进行操作, 从中提取出各结点

的坐标信息, 并对各结点编号, 生成结点表; 同时从. M ID 文

件中提取各街道的属性数据, 生成弧段表. 结点表和弧段表

( 格式如图 3 所示) 一起作为拓扑文件表示了网络的拓扑结

构. 当地图更新时, 只需重新生成结点表和弧段表, 然后就能

从中提取出网络的拓扑结构, 并用适当的数据结构来表示. 对

于A rc Info , 针对其 shap ef ile 文件能够根据同样的处理思路

来提取网络的拓扑结构.

图 3　结点表和弧段表的格式

F ig. 3 T he fo rm a t o f no de tab le and a rc tab le

表示网络的数据结构有很多, 例如邻接矩阵、 邻接表、 十

字链表等. 以往的研究证明针对最短路径分析, 表示网络的数
〔3〕.
据结构中最有效的是 Fo rw a rd S ta r 表示法 该表示法使用

两个数组来表示网络的拓扑关系. 一个数组存储和弧相关的

数据, 另一个数组存储和结点相关的数据. 网络中所有的弧按

照一定的顺序排列在数组中, 即以结点 1, 2, 3, 为起点的

© 1995- Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

1392 小　型　微　型　计　算　机　系　统 　　　　　　　 年

弧在数组中顺序排列, 起点相同的弧则能够任意排列. 弧的属

性数据, 如起点、 终点、 权值等, 以某种方式和弧保存在一起.

对于结点数组, 第 i 个元素和结点 i 相对应, 它存储的是以结

点 i 为起点的第一条弧在与弧相关的数组中的位置.

4　最短路径算法

我们所讨论的最短路径算法主要针对平面有向图, 一些

相关定义如下:

定义 1　有向图 G= {N , A }, N 为结点集合, A 为弧的集 合; 结点数 n = ûN û, 弧数m = ûA û; s 表示源结点, t 表示目的
结点.

定义 2 d ( i) 表示源结点 s 到结点 i 的加权距离; l ( i, j) 表

示连接结点 i 和 j 的弧的权值; S ( j) 表示结点 j 的状态, 分为未 标记结点(un reached) , 临时标记结点( tem po ra r ily labe led)
和永久标记结点(p e rm anen t ly labe led) 三种状态.
〔2〕
经典的最短路径算法—D ijk st ra 算法 是当前多数系统 解决最短路径问题采用的理论基础, 其求解源结点 s 到目的

结点 t 的最短路径的基本过程如下:

( 1) 初始化网络. 对所有结点 i, 如果 i≠s, 则 d ( i) ←+

∞, S ( i) = un reached, 否则 d ( i) = 0, S ( i) = p e rm a2

nen t ly labe led;

(2) T ←N ;

(3) 从 T 中取出权值最小的结点 k , d (k ) = m in〔d ( j) , j∈T 〕;S (k ) = p e rm anen t ly labe led;

(4) 如果 k = t, 则算法结束;

( 5) 对于和 k 相连的每个结点 j, j∈T. 如果 d ( j) > d (k ) + l (k , j) , 则 d ( j) ←d (k ) + l (k , j) , S ( j) = tem po ra r ily labe led;
(6) T ←T - {k }, 转到步骤(3).

由于算法将临时标记结点以无序的形式存放在一个链表

或数组中. 那么要选择一个权值最小的结点就必须把所有的

点都扫描一遍. 在大数据量的情况下, 这无疑是一个制约计算

速度的瓶颈. 从对D ijk st ra 算法的分析中能够看出, 步骤(3)

是算法的核心步骤. 实现它有两个关键问题要解决:

(1) 采用何种策略从 T 中选择权值最小的结点;

(2) 使用什么样的数据结构来维护 T 中的所有结点.

常见的选择策略有 F IFO ( F ir st In F ir st O u t ) , L IFO (L a st In F ir st O u t) 和B F S (B e st2F ir st2Sea rch ). 对于B F S 策
略, 临时标记结点中权值最小的结点被认为是最好的结点. 支

持以上搜索策略的数据结构较常见的有数组、 单双链表、 堆

栈、 哈希散列和队列等.

自从D ijk st ra 于 1959 年率先提出最短路径的求解算法

以来, 相继有不少新的最短路径算法被提出. C he rka ssky 等

人于 1993 年从已有的最短路径算法中选择了比较有代表性

的 17 种最短路径算法进行测试, 测试结果表明: 没有哪一种
〔1〕
算法能够适应所有类型的网络 . 这些算法的具体内容能够

参见文献〔1〕.总体来说, 这些算法采用的数据结构及其实现

方法由于受到当时计算机硬件发展水平的限制, 将空间存储

问题放到了一个很重要的位置, 以牺牲适当的时间效率来节

省空间. 当前, 空间存储问题已不再是要考虑的主要问题, 因

此能够对已有的算法重新考虑并进行改进. 结合文献〔1〕,我

们经过实验比较, 选择了D IKB (D ijk st ra’ s a lgo r ithm im p le2

m en ted w ith B ucke t s) 算法来对城市道路网进行最短路径分

析.

D IKB 算法相对于传统的D ijk st ra 算法的改进之处主要

体现在: 所有弧的权值都先转化为整数值(最大的权值记为

C ) , 而所有的临时标记结点则用一个B ucke t 序列来维护. B ucke t 序列中所有的B ucke t 按 0, 1, 2, 3, 4, 进行编号,

第 i 个B ucke t 内装有权值为 i 的临时标记结点, 每一个B uck2

e t 实际上是一个 F IFO (F ir st In F ir st O u t) 队列. 第一个非空

的B ucke t 内的每一个临时标记结点都是当前权值最小的结

点. 当一个结点的权值和状态发生变化时, 它在B ucke t s 序列

中的位置也要相应改变. 举例来说, 对于权值为 d (1) 的临时

标记结点 i, 若结点 i 的权值变为 d ( 2) , 则要将它相应地从

B ucke t d (1) 移到新的B ucke t d (2) 中; 若结点 i 变为永久标记 结点, 则要将它从B ucke t d (1) 中删除. D IKB 算法的其它处理 步骤和传统的D ijk st ra 算法类似, 不再详述. D IKB 算法流程 框图如图 4 所示.

图 4 D IKB 算法流程框图

F ig. 4 T he f low cha r t o f D IKB a lgo r ithm

为了进一步优化算法, 我们在算法的实现中设置了一个

索引L , L 的初始值为 0, 所有满足 i< L 的B ucke t 都为空. 下

一个要扫描的结点直接从B ucke t L 中取出, 若B ucke t L 为

空, 则L + 1. 在D IKB 算法中, 虽然为了维护B ucke t 序列需要

占用一定的内存资源, 但由于与B ucke t 相关的操作的复杂度

仅为O (1) , 因而大大提高了算法的执行效率, 这些操作包括:

(1) 检查一个B ucke t 是否为空;

(2) 在一个B ucke t 中增加一个元素;

( 3) 从一个B ucke t 中删除一个元素. 最坏情况下, D IKB
算法的时间复杂度是O (m + nC )〔1〕.

© 1995- Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

7 期　　　　　　　 刘云翔等: 基于城市道路网的最短路径分析解决方案 　　 1393

5　小　结

我们在最短路径分析系统中对各项关键技术进行了研究

和验证, 并在具有 9844 个结点, 31835 条弧段的实验用地图

( 其规模相当于省会级城市典型地图) 上进行了实际测试(试

验计算机配置为C e le ro n II 566, 128M B 内存). 在地图上选择

图 5　最短路径分析系统演示

F ig. 5 T he dem o n st ru t io n o f sho r te st p a th ana ly sis sy stem

了起点和终点后, 两点之间的最短路径可在 1 秒内计算出, 并

在地图上加以渲染(如图 5 所示, S ta r t 和 E nd 之间的粗线代

表了起点和终点之间的最短路径, 下面的总加权距离即为该

最短路径上各弧段的总权值). 算法的实现效率能够满足 110

报警、 119 火警等应急系统的应用需求.

测试结果如表 2 所示:

表 2　测试结果

T ab le 2 T he re su lt o f exp e r im en t

最快执 最慢执 平均执
结点数 弧数 最小弧长最大弧长
行时间 行时间 行时间

9844 31833 4 10479 0. 004 s 0. 995s 0. 373s


Ref eren ce:

1
C he rka ssky B V ,
Go ldbe rg A V , and R adzik T.
Sho r te st p a th s

a lgo r ithm s:
theo ry and exp e r im en ta l eva lua t io n〔R 〕.
T echn ica l

R epo r t 93 1480,
Com p u te r Science D ep a r tm en t,
S tanfo rd U n i

ve r sity. 1993.

2
D ijk st ra E W. A
no te o n tw o p ro b lem s in co nnect io n w ith g rap h s

〔J 〕. N um e r iche M a them a t ik. 1959, 1: 269～ 271

3
B en jam in Zhan F.
T h ree fa ste st sho r te st p a th a lgo r ithm s o n rea l

ro ad ne tw o rk s: da ta
st ructu re s and p ro cedu re s〔J 〕.
Jo u rna l o f

Geo g rap h ic Info rm a t io n and D ecisio n A na ly sis, 1995, 1 (1) : 69～

82

4
D ia l R B. A lgo r ithm
360:
sho r te st p a th fo re st w ith
topo lo g ica l

o rde r ing〔J 〕.
Comm un ica t io n s o f the A CM ,
1969,
12,
632～ 633
5
2

2
S tudy o n a ro u t ing a lgo r ithm ba sed o n
Yu Do ng ka i, L iu Yu
shu.

Ichno g rap hy 〔J 〕. Jo u rna l
o f B e ijing In st itu te o f T echno lo gy,

, 21 (1) : 31～ 34
2
2

6
2

2
T he ca lcu la t io n o f
T ang W en w u, Sh i X iao do ng, Zhu D a ku i.

the sho r te st p a th
u sing m o d if ied D ijk st ra a lgo r ithm in G IS〔J 〕.

Jo u rna l o f Im age and G rap h ics, , 5 (A ) (12) : 1019～ 1023
7
L e i Yang, Go ng J ian ya. A n eff icien t im p lem en ta t io n fo sho r te st

p a th a lgo r ithm ba sed o n D ijk st ra a lgo r ithm〔J 〕.Jo u rna l o f W uhan

T echn ica l U n ive r sity o f Se rvey ing and M app ing,
1999, 24 ( 3 ) :

209～ 212 2

2
附中文参考文献:

5 于东凯, 刘玉树. 基于平面图的最短路径算法的研究〔J 〕. 北京理 工大学学报, , 21 (1) : 31～ 34

6 唐文武, 施晓东, 朱大奎. G IS 中使用改进的D ijk st ra 算法实现 最短路径的计算〔J 〕. 中国图象图形学报, , 5 (A ) (12) : 1019
～ 1023

7 乐阳, 龚健雅. D ijk st ra 最短路径算法的一种高效率实现〔J 〕. 武

汉测绘科技大学学报, 1999, 24 (3) : 209～ 212

© 1995- Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.