An Improved SPFA Algorithm for Single-Source Shortest Path Problem Using Forward Star Data Structure
International Journal of Managing Information Technology (IJMIT)
ISSN: 0975-5586 (Online); 0975-5926 (Print)
Article:
An Improved SPFA Algorithm for Single-Source Shortest Path Problem Using Forward Star Data Structure
Authors
Xin Zhou, Kyushu University, Japan
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.
Keywords
SPFA; single source; shortest path; queue; MinPoP principle
Paper URL: http://airccse.org/journal/ijmit/papers/6114ijmit02.pdf
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.
SPFA; single source; shortest path; queue; MinPoP principle
Abstract URL:
http://airccse.org/journal/ijmit/vol6.html
http://airccse.org/journal/ijmit/vol6.html
Comments
Post a Comment