TY - GEN

T1 - An efficient algorithm for the Single-Source Shortest Path Problem in graph theory

AU - Li, Tianrui

AU - Qi, Luole

AU - Ruan, Da

PY - 2008

Y1 - 2008

N2 - The Single-Source Shortest Path problem (SSSP), known as the basis of many application areas, is a fundamental matter in graph theory. In this paper, a new efficient algorithm named Li-Qi (LQ) is proposed for SSSP to find a simple path of minimum total weights from a designated source vertex to each vertex. The algorithm is based on the ideas of the queue and the relaxation, The main differences between this strategy with the Breadth-first search and the Bellman-Ford algorithm are that the vertices may be queued more than once and only the source vertex and relaxed vertices are queued; the algorithm terminates when the queue is empty. Experimental evaluation on different sizes of the generated graphs validates that the proposed algorithm far outperforms the simplest implementation of the Dijkstra's algorithm and surpasses the Bellman-Ford algorithm by about 2 times.

AB - The Single-Source Shortest Path problem (SSSP), known as the basis of many application areas, is a fundamental matter in graph theory. In this paper, a new efficient algorithm named Li-Qi (LQ) is proposed for SSSP to find a simple path of minimum total weights from a designated source vertex to each vertex. The algorithm is based on the ideas of the queue and the relaxation, The main differences between this strategy with the Breadth-first search and the Bellman-Ford algorithm are that the vertices may be queued more than once and only the source vertex and relaxed vertices are queued; the algorithm terminates when the queue is empty. Experimental evaluation on different sizes of the generated graphs validates that the proposed algorithm far outperforms the simplest implementation of the Dijkstra's algorithm and surpasses the Bellman-Ford algorithm by about 2 times.

KW - Single-Source Shortest Path problem (SSSP)

KW - Graph theory

UR - http://www.scopus.com/inward/record.url?scp=60349089680&partnerID=8YFLogxK

U2 - 10.1109/ISKE.2008.4730916

DO - 10.1109/ISKE.2008.4730916

M3 - In-proceedings paper

AN - SCOPUS:60349089680

SN - 9781424421978

T3 - Proceedings of 2008 3rd International Conference on Intelligent System and Knowledge Engineering, ISKE 2008

SP - 152

EP - 157

BT - Proceedings of 2008 3rd International Conference on Intelligent System and Knowledge Engineering, ISKE 2008

PB - IEEE - Institute of Electrical and Electronics Engineers

T2 - Proceedings of 2008 3rd International Conference on Intelligent System and Knowledge Engineering, ISKE 2008

Y2 - 17 November 2008 through 19 November 2008

ER -