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 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

Paper URL: 
Current Issue URL:

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

Network Media Attention and Green Technology Innovation

 #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 Network Media Attention and Green Technology Innovation Authors Long Lingxiao and Fan Yipeng 1Business School, Sichuan University, Chengdu, China Abstract   This paper will provide a novel empirical study for the relationship between network media attention and green technology innovation and examine how network media attention can ease financing constraints. It collected data from listed companies in China's heavy pollution industry and perf...
Read more