Dijkstra最短路径算法的一种高效率实现

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

Dijkstra最短路径算法的一种高效率实现

乐阳, 龚健雅

文章导航 > 武汉大学学报 ● 信息科学版 > 1999 > 24(3): 208-212

乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉大学学报 ● 信息科学版, 1999, 24(3): 208-212.

引用本文:

乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉大学学报 ● 信息科学版, 1999, 24(3): 208-212.

Yue Yang, Gong Jianya. An Efficient Implementation of Shortest Path Algorithm Based on Dijkstra Algorithm[J]. Geomatics and Information Science of Wuhan University, 1999, 24(3): 208-212.

Citation:

Yue Yang, Gong Jianya. An Efficient Implementation of Shortest Path Algorithm Based on Dijkstra Algorithm[J]. Geomatics and Information Science of Wuhan University, 1999, 24(3): 208-212.

Dijkstra最短路径算法的一种高效率实现

乐阳,
龚健雅

武汉测绘科技大学测绘遥感信息工程国家重点实验室, 武汉市珞喻路129号, 430079

基金项目: 国家杰出青年科学基金和国家"九五"重点科技攻关资助项目,编号49525101 及96-B02-03

作者简介:
乐阳,女, 26岁,硕士,现从事GIS空间分析研究

中图分类号: P208;O22

An Efficient Implementation of Shortest Path Algorithm Based on Dijkstra Algorithm

National Laboratory for Information Engineering in Surveying, Mapping and Remote Sensing, WTUSM, 129 Luoyu Road, Wuhan, China, 430079

摘要: 在已存在的一些最短路径算法测试总结的基础上,根据GIS中网络计算的实际情况,从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手,提出了一种Dijkstra最短路径算法的高效率实现方法。
- 最短路径算法 /
- 网络分析 /
- 地理信息系统
Abstract: With the development of geographic information science and the wide use of GIS software, more and more needs are required to the network analyses. As the key of network analyses, computing the shortest paths over a network is an important problem that scholars facus on. Start with the data structure during its computation process and combined with F.Benjamin Zhan's evaluation of a set of 15 shortest path algorithms, this paper presents an efficient method of realize the shortest path algorithm which is based on Dijkstra algorithm. Result shows that this method performs well in practice.
- shortest path algorithm /
- network analysis /
- GIS

[1]	王家耀. 关于地理信息系统未来发展的思考 . 武汉大学学报 ● 信息科学版, 2022, 47(10): 1535-1545. doi: 10.13203/j.whugis20210679
[2]	刘耀林, 方飞国, 王一恒. 基于手机数据的城市内部就业人口流动特征及形成机制分析——以武汉市为例 . 武汉大学学报 ● 信息科学版, 2018, 43(12): 2212-2224. doi: 10.13203/j.whugis20180140
[3]	汤青慧, 唐旭, 崔晓晖, 胡石元, 刘耀林. 基于动态通达网络模型的最优航程规划方法 . 武汉大学学报 ● 信息科学版, 2015, 40(4): 521-528. doi: 10.13203/j.whugis20140387
[4]	曾文, 敖卿鑫, 杨之江. 适用于关阀分析算法的供水管网单元-阀门图模型 . 武汉大学学报 ● 信息科学版, 2014, 39(12): 1441-1445.
[5]	陈建群, 吴勰, 王振兴, 朱建军. 鄱阳湖湿地地理信息系统建设及其关键技术研究 . 武汉大学学报 ● 信息科学版, 2012, 37(8): 888-891.
[6]	杨传勇, 胡海, 胡鹏, 曹枫. 欧氏障碍空间的最短路径问题解法 . 武汉大学学报 ● 信息科学版, 2012, 37(12): 1495-1499.
[7]	王浩, 潘少明, 彭敏, 李锐. 数字地球中影像数据的Zipf-like访问分布及应用分析 . 武汉大学学报 ● 信息科学版, 2010, 35(3): 356-359.
[8]	白轶多, 胡鹏, 夏兰芳, 郭峰林. 关于k次短路径问题的分析与求解 . 武汉大学学报 ● 信息科学版, 2009, 34(4): 492-494.
[9]	喻占武, 李忠民, 郑胜. 基于对象存储的新型网络GIS体系结构研究 . 武汉大学学报 ● 信息科学版, 2008, 33(3): 285-288.
[10]	陈志荣, 刘仁义, 徐财江, 刘南. 一种面向网络发布的海洋遥感数据库引擎 . 武汉大学学报 ● 信息科学版, 2007, 32(12): 1107-1110.
[11]	陈玉敏, 龚健雅. 基于模糊数学的多因素道路网权值确定算法 . 武汉大学学报 ● 信息科学版, 2007, 32(10): 928-931.
[12]	王海军. 基于注水模型的网络分析方法研究 . 武汉大学学报 ● 信息科学版, 2007, 32(5): 419-422.
[13]	郑年波, 李清泉, 徐敬海, 宋莺. 基于转向限制和延误的双向启发式最短路径算法 . 武汉大学学报 ● 信息科学版, 2006, 31(3): 256-259.
[14]	李国建, 胡鹏. GIS中的数据转换与代数同构分析 . 武汉大学学报 ● 信息科学版, 2000, 25(4): 312-317.
[15]	马飞. 数学形态学在遥感和地理信息系统数据分析与处理中的应用研究 . 武汉大学学报 ● 信息科学版, 1998, 23(2): 187-187.
[16]	龚健雅, 朱欣焰, 李爱勤, 吴华意. 地理信息系统基础软件吉奥之星NT版的总体设计思想与关键技术 . 武汉大学学报 ● 信息科学版, 1997, 22(3): 187-190,194.
[17]	马飞, 李德仁. 数学形态学在GIS空间分析中的应用 . 武汉大学学报 ● 信息科学版, 1996, 21(1): 41-45,49.
[18]	李清泉, 李德仁. 三维地理信息系统中的数据结构 . 武汉大学学报 ● 信息科学版, 1996, 21(2): 128-133.
[19]	蓝运超, 杨仁. 城市系统规划与遥感、地理信息系统技术 . 武汉大学学报 ● 信息科学版, 1991, 16(1): 85-91.
[20]	李秋萍, 陈宇, 栾学晨. 利用网络游记分析不同类型游客的旅游流网络特征差异——以云南省为例 . 武汉大学学报 ● 信息科学版, 0, 0(0): 0-0. doi: 10.13203/j.whugis20210045

WeChat

点击查看大图

计量

文章访问数: 2261
HTML全文浏览量: 565
PDF下载量: 1183
被引次数: 0

Dijkstra最短路径算法的一种高效率实现

乐阳,
龚健雅

武汉测绘科技大学测绘遥感信息工程国家重点实验室, 武汉市珞喻路129号, 430079

基金项目: 国家杰出青年科学基金和国家"九五"重点科技攻关资助项目,编号49525101 及96-B02-03

作者简介:
乐阳,女, 26岁,硕士,现从事GIS空间分析研究

收稿日期: 1999-01-27
刊出日期: 1999-03-05

中图分类号: P208;O22

关键词:

最短路径算法 /

地理信息系统

摘要: 在已存在的一些最短路径算法测试总结的基础上,根据GIS中网络计算的实际情况,从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手,提出了一种Dijkstra最短路径算法的高效率实现方法。

English Abstract

乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉大学学报 ● 信息科学版, 1999, 24(3): 208-212.

引用本文:

乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉大学学报 ● 信息科学版, 1999, 24(3): 208-212.

Yue Yang, Gong Jianya. An Efficient Implementation of Shortest Path Algorithm Based on Dijkstra Algorithm[J]. Geomatics and Information Science of Wuhan University, 1999, 24(3): 208-212.

Citation:

Yue Yang, Gong Jianya. An Efficient Implementation of Shortest Path Algorithm Based on Dijkstra Algorithm[J]. Geomatics and Information Science of Wuhan University, 1999, 24(3): 208-212.

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

我要投稿

投稿攻略

联系我们

二维码