改进的Dijkstra算法在风暴潮系统中的应用
需积分: 9 47 浏览量
2012-04-12
11:07:04
上传
评论
收藏 1.15MB PDF 举报
—275—
改进的
Dijkstra
算法在风暴潮系统中的应用
黄冬梅，方 钱
(上海海洋大学信息学院，上海 201306)
摘 要：针对风暴潮系统需要计算受灾区域到多个安置点的最短路径，并根据受灾人数和安置点的容量进行人员撤离的情况，提出对
Dijkstra 算法的改进方案，其中包括最短路径排序和多目标撤离。采用 Matlab 进行仿真。实验结果表明，对算法的改进是有效可行的，能
够使多目标撤离路径的计算次数由多次减少到一次。
关键词：风暴潮系统；Dijkstra 算法；最短路径；撤离
Application of Improved Dijkstra Algorithm in Storm Surge System
HUANG Dong-mei, FANG Qian
(College of Information Technology, Shanghai Ocean University, Shanghai 201306, China)
【Abstract】In allusion to the storm surge system’s requirement: it is necessary to figure out the shortest path from the disaster area to
multi-settlements, then to evacuate the victims based on the number of disaster victims and the capacity of the settlements, this paper presents two
improvements of Dijkstra algorithm, including sorting the shortest paths and evacuating to multitargets. An emulation is carried out based on Matlab,
and it turns out that the improvement of the algorithm is effective and feasible, which can reduce the times of figuring out the path of evacuating to
multitargets from several to one.
【Key words】storm surge system; Dijkstra algorithm; the shortest path; evacuation
计 算 机 工 程
Computer Engineering
第 36 卷 第 20 期
Vol.36 No.20
2010 年 10 月
October 2010
·开发研究与设计技术·
文章编号：1000—3428(2010)20—0275—02
文献标识码：A
中图分类号：N945
1
概述
网络分析
[1]
是
GIS
最主要的功能之一，在信息查询、辅
助决策等多个领域中发挥着重要的作用，而网络分析中最基
本最关键的问题是最优路径问题
[2,3]
。解决最优路径的方法很
多，如图论方法、动态规划法、
A*
算法、遗传算法和神经网
络等。在图论中有几十种求解算法
[4]
，其中，
Dijkstra
算法是
目前多数系统解决最优路径问题采用的理论基础，被
GIS
系
统广泛采用。在风暴潮系统中，需要根据受灾情况，选择受
灾点到安置点的最优路径进行人员撤离。
Dijkstra
算法只用于
求出单源最短路径，而在撤离过程中还需要将人员安置到多
个安置点，所以，在本文中对其进行了两点改进：将受灾点
到安置点的最短路径按长度的降序排列；将人员撤离到多个
安置点，即多目标撤离。
2
问题描述
单源最短路径问题
[5-6]
是：给定带权的有向图
G
=(
V
,
E
)
和
图中节点
s
∈
V
，求从
s
到其余各节点的最短路径，其中，
s
称为源点。路径长度是指路径上的边所带权值之和，而不是
路径上的边的数目，并假定边上的权值为非负值。
用贪心法
[7]
的观点看，源点到另一个节点的任何一条路
径可视为一个可行解，其中长度最短的路径是从源点到该节
点的最短路径。从源点到其余每个节点的最短路径构成了单
源最短路径问题的最优解。因此，问题解的形式可以认为是：
L=(L
1
,L
2
,
…
, L
n
-1
)
，只要每个分量都是源点到某一个节点的路
径，
L
就是问题的一个可行解。
Dijkstra
算法提出了按路径长度的非递减次序逐一产生
最短路径的算法：首先求得长度最短的一条路径，再求得长
度次短的一条路径，以此类推，直到源点到其他所有节点之
间的最短路径都已求得为止。
在风暴潮系统中，受灾区域的人员需要同时迅速撤离到
多个安置点，而
Dijkstra
算法只方便用于求解单条最短路径，
因此，基于
Dijkstra
算法做以下改进：
(1)
求出受灾区域到各
个安置点的最短路径；
(2)
受灾人员多目标撤离。
3 Dijkstra
算法
设集合
S
存放已经求得的最短路径的终点，则
V-S
为尚
未求得最短路径的终点集合。初始状态时，集合
S
中只有一
个源点，设为节点
s
。
Dijklstra
算法的具体做法是：首先将源
点
s
加入
S
中；在算法的每一步中，按照最短路径值的非减
次序，产生下一条最短路径
(
s
->
t
)
，并将该路径的终点
t
V
∈
-S
加入
S
中；直到
S=V
，算法结束。
为了便于使用贪心法求解，先定义术语“当前最短路径”。
在算法执行中，一个节点
t
V
∈
-S
的当前最短路径，是一条从
源点
s
到节点
t
的路径，在该路径上除节点
t
外，其余节点都
属于
S
，当前最短路径是所有这些路径中最短的。于是可将
最优量度标准设计为：从
V-S
选择具有最短的“当前路径”
的节点加入集合
S
中。
为实现
Dijkstra
算法，设计如下数据结构：
(1)
一维数组
d
[
i
]
中存放从源点
s
到节点
i
的当前最短路径
的长度。
基金项目：海洋公益性行业科研专项经费基金资助项目“临港新城
风暴潮灾害评估与对策辅助决策系统研究”(200805016)；“基于 GIS
的城市风暴潮洪水演进模型和防灾减灾辅助决策”(08dz1204802)
作者简介：黄冬梅(1963－)，女，教授，主研方向：WebGIS，智能
信息处理，人机交互技术；方 钱，硕士研究生
收稿日期：2010-01-04 E-mail：qjfangqian@163.com
评论0
最新资源