An Efficient Algorithm for the Single-Source Shortest Path Problem in Graph Theory

摘要：

The Single-Source Shortest Path problem(SSSP),known as the basis of many application areas,is afundamental matter in graph theory.In this paper,anew efficient algorithm named Li-Qi(LQ)is proposedfor SSSP to find a simple path of minimum totalweights from a designated source vertex to each vertex.The algorithm is based on the ideas of the queue andthe relaxation,The main differences between thisstrategy with the Breadth-first search and the Bellman-Ford algorithm are that the vertices may be queuedmore than once and only the source vertex and relaxedvertices are queued;the algorithm terminates when thequeue is empty.Experimental evaluation on differentsizes of the generated graphs validates that theproposed algorithm far outperforms the simplestimplementation of the Dijkstras algorithm andsurpasses the Bellman-Ford algorithm by about 2times.

作者: Tianrui Li Luole Qi Da Ruan

作者单位: School of Information Science and Technology Southwest Jiaotong University,Chengdu,610031,China The Belgian Nuclear Research Centre(SCK·CEN)Boeretang 200,B-2400 Mol,Belgium.& Dept.of Applied Math

会议类型: 国际会议

会议名称: 2008 3rd International Conference on Intelligent System and Knowledge Engineering(第三届智能系统与知识工程国际会议)(ISKE 2008)

会议地点: 厦门

会议语种:英文

页码: 152-157

在线出版日期: 2008-11-17（万方平台首次上网日期，不代表论文的发表时间）