Research on the Improvement of Dijkstra Algorithm in the Shortest Path Calculation

DOI

10.2991/macmc-17.2018.141How to use a DOI?

Keywords

Dijkstra Algorithm, Improvement, Water inrush disaster, The best water avoidance path, Equivalent path

Abstract

Dijkstra Algorithm is proposed by Holland computer scientist Dijkstra in 1959, and it is a typical shortest path algorithm, which can implement the shortest path planning in directed graphs. However, the traditional Dijkstra algorithm can only compute simple shortest path planning problems, but it is not suitable for complex situations. Based on a project, this paper proposed an improved method of Dijkstra Algorithm. First, this paper interprets the Dijkstra Algorithm before being improved, and uses it to calculate the mine shortest path to avoid water, and then a method for improvement will be proposed later to introduce the concept of equivalent path and analyze the influence factor and weight of equivalent path. The conversion formula of the equivalent path and actual path will be obtained finally in the paper, where the equivalent path can realize the adaptive improvement to the Dijkstra algorithm, and calculate on the best path to avoid water when the water inrush occurs.

Copyright

© 2018, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Yong Huang
PY  - 2018/01
DA  - 2018/01
TI  - Research on the Improvement of Dijkstra Algorithm in the Shortest Path Calculation
BT  - Proceedings of the 2017 4th International Conference on Machinery, Materials and Computer (MACMC 2017)
PB  - Atlantis Press
SP  - 745
EP  - 749
SN  - 2352-5401
UR  - https://doi.org/10.2991/macmc-17.2018.141
DO  - 10.2991/macmc-17.2018.141
ID  - Huang2018/01
ER  -