基于城市道路网的最短路径分析解决专业方案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.