MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

Analysis and Comparison between the Algorithm Time Efficiency of Dijkstra and SPFA

Xinfeng Xie Nan’an No.1 Middle School of Fujian

S.-T. Yau High School Science Awarded Papers mathscidoc:1608.35137

Dongrun-Yau Science Award, 2013
Dijkstra and Bellman-ford are the two basic methods to solve Single-source shortest paths problem，and SPFA is the optimized version of Bellman-ford. However, since the algorithm time complexity is 0 (kn), SPFA’s time efficiency has some instabilities. This paper will compare the time efficiency between Dijkstra optimized with heap and three kinds of SPFA in different density graphs. Meanwhile, random data is created to test optimized Dijkstra and 3 types of SPFA. Finally, according to the calculation result of two methods’ time efficiency, some suggestion is given for their application under different situation.
Dijkstra, SPFA, algorithm time efficiency, Application of shortest path algorithm
[ Download ] [ 2016-08-18 13:53:46 uploaded by yauawardadmin ] [ 1113 downloads ] [ 0 comments ] 
@inproceedings{xinfeng2013analysis,
  title={Analysis and Comparison between the Algorithm Time Efficiency of Dijkstra and SPFA},
  author={Xinfeng Xie},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160818135346479541229},
  booktitle={Dongrun-Yau Science Award},
  year={2013},
}
Xinfeng Xie. Analysis and Comparison between the Algorithm Time Efficiency of Dijkstra and SPFA. 2013. In Dongrun-Yau Science Award. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160818135346479541229.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved