An Improved SPFA Algorithm for Single-Source Shortest Path Problem Using Forward Star Data Structure

Xin Zhou Department of Economic Engineering, Kyushu University, Fukuoka 812-8581, 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  

More Details


Comments

Post a Comment

Popular posts from this blog

Engineering Life Cycle Enables Penetration Testing and Cyber Operations

 #managinginformation #electronicbilling #education #greentechnologies #informationtechnology #embeddedsystems #electronicvoting #financialmarkets #healthcaremarketing #digitalproducts #socialdevelopment #fashion #management #marketingoperations #yieldmanagement #opensourcesoftware #vendormanagedinventory #mobile #mobilephotography #systems #telecommunication #management #chain #supplychainmanagement #supply #valuechain #business #marketing #businesstobusinessmarketing #knowledgemanagement #qualitycontrol #economicissues #vendormanagement Engineering Life Cycle Enables Penetration Testing and Cyber Operations Authors Paul Cheney1and Ian R. McAndrew2 1Department of Critical Infrastructure Protection, Capitol Technology University, Laurel MD., USA 2Capitol Technology University, Laurel MD., USA Abstract   This paper discusses the strengths and weaknesses of proper engineering and life cycle management on higher level cyber security operations. Rushing innovation and increasing p...
Read more
Image
    International Journal of Managing Information Technology (IJMIT)  WJCI Indexed ISSN: 0975-5586 (Online); 0975-5926 (Print) http://airccse.org/journal/ijmit/ijmit.html Call for Papers! IJMIT is indexed in World Journal Clout Index (WJCI) https://wjci.cnki.net/UserIndex/JournalOverseaDetails?filename=701675 Contact us:  ijmitjournal@aircconline.com  or  ijmit@airccse.org Submission Url http://coneco2009.com/submissions/imagination/home.html    
Read more

Top 20 Cited Research Articles in Information Management - 2021

Image
    International Journal of Managing Information Technology (IJMIT) ISSN: 0975-5586 (Online); 0975-5926 (Print) http://airccse.org/journal/ijmit/ijmit.html Call for Papers! Academia Post: Top 20 Cited Research Articles in Information Management - 2021 Academia Link: https://www.academia.edu/49079351/Top_20_Cited_Research_Articles_in_Information_Management_2021
Read more