research-article

Application of Improved Dijkstra Algorithm in Two-dimensional Path Planning Problem

Authors:

Zhang Ruifang,

Ji Tianyi,

Zheng HaitaoAuthors Info & Claims

ICIIP '19: Proceedings of the 4th International Conference on Intelligent Information Processing

Pages 211 - 215

https://doi.org/10.1145/3378065.3378106

Published: 08 April 2020 Publication History

Get Access

Abstract

The Dijkstra algorithm is a typical single-source shortest path algorithm for calculating the shortest path from one node to the other in a non-negative weight map, but its use of the roulette method greatly affects the node selection. Speed and efficiency. Therefore, on the basis of ensuring the search accuracy, this paper improves the initial Dijkstra algorithm to improve the efficiency of the algorithm and meet its needs in 2D or 3D path planning. In this paper, MATLAB2018a is used as the experimental platform to simulate the initial Dijkstra algorithm and the improved Dijkstra algorithm. The experimental results show that the improved algorithm greatly reduces the path planning vision and improves the operating efficiency.

References

[1]

Wolfgang Fink, Victor R. Baker, Alexander J. W. Brooks, Michael Flammia, James M. Dohm, Mark A. Tarbell. Globally optimal rover traverse planning in 3D using Dijkstra's algorithm for multi-objective deployment scenarios[J]. Planetary and Space Science,2019

Google Scholar

[2]

Gao Xincheng, Liu Deju, Wang Lili, Ma Shuxuan. Design and Optimization of QOS Routing Model Based on Ant Colony Algorithm[J]. Journal of Shaanxi University of Technology(Natural Science Edition), 2019(02):67--72.

Google Scholar

[3]

Wu Xiaonian, Yan Yuang, Zhang Runlian. A hybrid path planning algorithm based on genetics and ant colony in DEM [J/OL]. Computer Application Research: 1--5 [2019-09-21].

Google Scholar

[4]

Liu Guofeng. Research on Path Planning of Industrial Manipulator Based on Ant Colony Algorithm[J]. Internal Combustion Engines & Parts, 2019(16):119--121.

Google Scholar

[5]

Wang Haifeng, Chen Jingming, Wang Guangmin. Study on Optimization of Rural Garbage Recycling Route Based on Improved Distance and Ant Colony Algorithm[J]. Environmental Sanitation Engineering, 2019, 27(04):87--92

Google Scholar

[6]

Wang Zhaonan. Research and Implementation of Optimal Path Calculation Method for Massive Data Based on Dijkstra Algorithm[J]. Bulletin of Surveying and Mapping, 2012(09):32--34+37.

Google Scholar

[7]

Chen Honglu, Deng Yiran. Study on Large Building Escape Scheme Based on Game Theory and Dijkstra Algorithm[J/OL]. Digital Technology and Application: 1--7 [2019-09-21].

Google Scholar

[8]

Wang Shuxi, Li Anzhen. Multiple Adjacent Points and Multiple Shortest Path Problems in Dijkstra Algorithm[J]. Computer Science, 2014, 41(06):217--224.

Google Scholar

[9]

Wang Zhihe, Ling Yun. Optimization and Implementation of Dijkstra Shortest Path Algorithm[J]. Control & Automation,2007(33):275--277

Google Scholar

[10]

Le Yang, Gang Jianya. A High Efficiency Implementation of Dijkstra Shortest Path Algorithm[J]. Journal of Wuhan Institute of Surveying and Mapping, 1999(03):209--212.

Google Scholar

Cited By

View all

Fan BGuo L(2023)An Improved JPS Algorithm for Global Path Planning of the Seabed Mining VehicleArabian Journal for Science and Engineering10.1007/s13369-023-08232-749:3(3963-3977)Online publication date: 12-Sep-2023
https://doi.org/10.1007/s13369-023-08232-7
Liu ZYang XTang WZhang XYang Z(2022)BACO: A Bi-Ant-Colony-Based Strategy for UAV Trajectory Planning with Obstacle Avoidance2022 18th International Conference on Mobility, Sensing and Networking (MSN)10.1109/MSN57253.2022.00055(279-286)Online publication date: Dec-2022
https://doi.org/10.1109/MSN57253.2022.00055

Index Terms

Application of Improved Dijkstra Algorithm in Two-dimensional Path Planning Problem
1. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Shortest paths

Recommendations

Shortest path problem with uncertain arc lengths

Uncertainty theory provides a new tool to deal with the shortest path problem with nondeterministic arc lengths. With help from the operational law of uncertainty theory, this paper gives the uncertainty distribution of the shortest path length. Also, ...
Path Planning Algorithm Using the Particle Swarm Optimization and the Improved Dijkstra Algorithm
PACIIA '08: Proceedings of the 2008 IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application - Volume 02

In this paper, we develop the path planning algorithm using the improved Dijkstra algorithm and the particle swarm optimization. To get the optimal path, at first we construct the MAKLINK on the world environment and then make a graph associated with the ...
Dijkstra's algorithm to find the nearest vaccine location
Abstract
Since the start of Covid-19 pandemic has made many people look for vaccine locations. In general, Dijkstra algorithm is used to find the shortest path. The shortest path problem concentrates on finding the path with the minimum distance. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICIIP '19: Proceedings of the 4th International Conference on Intelligent Information Processing

November 2019

528 pages

ISBN:9781450361910

DOI:10.1145/3378065

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

Guilin: Guilin University of Technology, Guilin, China
Wuhan University of Technology: Wuhan University of Technology, Wuhan, China
International Engineering and Technology Institute, Hong Kong: International Engineering and Technology Institute, Hong Kong

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 April 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ICIIP 2019

ICIIP 2019: 2019 4th International Conference on Intelligent Information Processing

November 16 - 17, 2019

China, China

Acceptance Rates

Overall Acceptance Rate 87 of 367 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
221
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fan BGuo L(2023)An Improved JPS Algorithm for Global Path Planning of the Seabed Mining VehicleArabian Journal for Science and Engineering10.1007/s13369-023-08232-749:3(3963-3977)Online publication date: 12-Sep-2023
https://doi.org/10.1007/s13369-023-08232-7
Liu ZYang XTang WZhang XYang Z(2022)BACO: A Bi-Ant-Colony-Based Strategy for UAV Trajectory Planning with Obstacle Avoidance2022 18th International Conference on Mobility, Sensing and Networking (MSN)10.1109/MSN57253.2022.00055(279-286)Online publication date: Dec-2022
https://doi.org/10.1109/MSN57253.2022.00055

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Shortest path problem with uncertain arc lengths

Path Planning Algorithm Using the Particle Swarm Optimization and the Improved Dijkstra Algorithm

Dijkstra's algorithm to find the nearest vaccine location