Shortest path algorithm confined to conditions in grid data model

• Database Technology • Previous Articles Next Articles

Shortest path algorithm confined to conditions in grid data model

Received:2007-10-25 Revised:1900-01-01 Online:2008-04-01 Published:2008-04-01
Contact: xiangyang SHE

栅格数据模型中附有条件的最短路径算法

厍向阳史经俭罗晓霞

西安科技大学西安科技大学

通讯作者: 厍向阳

Abstract

Abstract: The shortest path question confined in conditions was generalized as the shortest path question confined to point set, the shortest path question confined to edge set, and the shortest path question confined to attribute set. The shortest path algorithm confined to conditions in grid data mode was put forward. In this algorithm, graphic or network was expressed by grid data model, based on greedy idea. In the end, the algorithm was validated by examples. It is shown that the shortest path algorithm confined to conditions in grid data model is completely feasible and effective.

Key words: grid data, shortest path, point set constraint, edge set constraint, attribute set constraint

摘要： 将附有条件的最短路径概括为点约束、边约束和属性约束的最短路径问题。以栅格数据模型为图或网络描述方式，基于贪心算法思想，提出栅格数据模型中附有条件的最短路径算法。最后，通过实例进行了算法测试，结果表明栅格数据模型中附有条件的最短路径算法是完全可行和有效的。

关键词: 栅格数据, 最短路径, 点约束, 边约束, 属性约束

xiangyang SHE jingjian Shi . Shortest path algorithm confined to conditions in grid data model[J]. Journal of Computer Applications.

厍向阳史经俭罗晓霞. 栅格数据模型中附有条件的最短路径算法[J]. 计算机应用.

[1]	Yuan LI, Qiulan LIN, Anzhi CHEN, Guoli YANG, Wei SONG, Guoren WANG. Temporal shortest path counting query algorithm based on tree decomposition [J]. Journal of Computer Applications, 2024, 44(8): 2446-2454.
[2]	GAO Yilu, HU Zhihua. Path planning for automated guided vehicles based on tempo-spatial network at automated container terminal [J]. Journal of Computer Applications, 2020, 40(7): 2155-2163.
[3]	XIANG Xiong, TIAN Jian. P2P transmission scheduling optimization based on software defined network [J]. Journal of Computer Applications, 2020, 40(3): 777-782.
[4]	Ming DU, Anping YANG, Junfeng ZHOU, Ziyang CHEN, Yun YANG. Optimized algorithm for k-step reachability queries on directed acyclic graphs [J]. Journal of Computer Applications, 2020, 40(2): 426-433.
[5]	LIU Haohan, GUO Jingjing, LI Jianfu, HE Huaiqing. Improved multi-objective A^* algorithm based on random walk [J]. Journal of Computer Applications, 2018, 38(1): 116-119.
[6]	LI Zhuhong, ZHAO Canming, ZHOU Fang, ZHANG Xinming. Efficient and load balanced open shortest path first protocol in electric power communication network [J]. Journal of Computer Applications, 2017, 37(7): 1873-1876.
[7]	WEN Juping, HU Xiaosheng, LIN Dongmei, ZENG Yaguang. Graph reachability query based on reference node embedding [J]. Journal of Computer Applications, 2016, 36(7): 1998-2005.
[8]	QIU Jigang, LI Wenlong, YANG Jia. Path optimization algorithm for team navigation based on multiple point collaboration [J]. Journal of Computer Applications, 2015, 35(7): 2093-2095.
[9]	SHI Lei, SU Jinhai, GUO Yixi. Optimal routing selection algorithm of end-to-end key agreement in quantum key distribution network [J]. Journal of Computer Applications, 2015, 35(12): 3336-3340.
[10]	JING Yuan HUANG Guorong YANG Ming QI Yunjun CHEN Shangguang. Modeling and simulation for high-frequency IP wide-area network [J]. Journal of Computer Applications, 2014, 34(2): 333-337.
[11]	WANG Xiaolong ZHAO Lifeng. Steiner tree heuristic algorithm based on weighted node [J]. Journal of Computer Applications, 2014, 34(12): 3414-3416.
[12]	KONG Lingjing ZENG Huashen LI Yao. Secure protection scheme for hierarchical OSPF network [J]. Journal of Computer Applications, 2013, 33(08): 2212-2217.
[13]	ZHU Li-na LIANG Wei ZHAO Rui-lian BI Jing-ping. MTRM: real-time monitoring method for multi-protocol label switch traffic engineering tunnel [J]. Journal of Computer Applications, 2012, 32(07): 1812-1815.
[14]	ZHENG Bo-chuan SANG Yong-sheng. Lotka-Volterra recurrent neural network model for solving shortest path [J]. Journal of Computer Applications, 2012, 32(07): 1965-1968.
[15]	LI Chun-quan SHANG Yu-ling HU Chun-yang ZHU Pan-feng. Multi-granular resource access control for cloud manufacturing based on K-shortest path algorithm [J]. Journal of Computer Applications, 2011, 31(09): 2356-2358.