%0 Journal Article %1 noauthororeditor %A Zhou, Xin %D 2014 %J International Journal of Managing Information Technology (IJMIT) %K MinPoP SPFA path principle queue shortest single source %N 1 %P 1 to 7 %R 10.5121/ijmit.2014.6102 %T AN IMPROVED SPFA ALGORITHM FOR SINGLE SOURCE SHORTEST PATH PROBLEM USING FORWARD STAR DATA STRUCTURE %U http://airccse.org/journal/ijmit/papers/6114ijmit02.pdf %V 6 %X We present an improved SPFA algorithm for the single source shortest path problem. For a random graph, the empirical average time complexity is O(|E|), where |E| is the number of edges of the input network. SPFA maintains a queue of candidate vertices and add a vertex to the queue only if that vertex is relaxed. In the improved SPFA, MinPoP principle is employed to improve the quality of the queue. We theoretically analyse the advantage of this new algorithm and experimentally demonstrate that the algorithm is efficient.

@article{noauthororeditor, abstract = {We present an improved SPFA algorithm for the single source shortest path problem. For a random graph, the empirical average time complexity is O(|E|), where |E| is the number of edges of the input network. SPFA maintains a queue of candidate vertices and add a vertex to the queue only if that vertex is relaxed. In the improved SPFA, MinPoP principle is employed to improve the quality of the queue. We theoretically analyse the advantage of this new algorithm and experimentally demonstrate that the algorithm is efficient.}, added-at = {2020-01-10T07:04:43.000+0100}, author = {Zhou, Xin}, biburl = {https://www.bibsonomy.org/bibtex/2f625eaade53f64ed3a880a1d059ef070/ijmit_journal}, doi = {10.5121/ijmit.2014.6102}, interhash = {0cf019f26273284e03b719991a46ebd1}, intrahash = {f625eaade53f64ed3a880a1d059ef070}, issn = {ISSN: 0975-5586 (Online); 0975-5926 (Print)}, journal = {International Journal of Managing Information Technology (IJMIT)}, keywords = {MinPoP SPFA path principle queue shortest single source}, language = {English}, month = {February}, number = 1, pages = {1 to 7}, timestamp = {2020-01-10T07:04:43.000+0100}, title = {AN IMPROVED SPFA ALGORITHM FOR SINGLE SOURCE SHORTEST PATH PROBLEM USING FORWARD STAR DATA STRUCTURE}, url = {http://airccse.org/journal/ijmit/papers/6114ijmit02.pdf}, volume = 6, year = 2014 }