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

Tianrui Li, Luole Qi, Da Ruan

    Research outputpeer-review

    Abstract

    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.

    Original languageEnglish
    Title of host publicationProceedings of 2008 3rd International Conference on Intelligent System and Knowledge Engineering, ISKE 2008
    PublisherIEEE - Institute of Electrical and Electronics Engineers
    Pages152-157
    Number of pages6
    ISBN (Print)9781424421978
    DOIs
    StatePublished - 2008
    EventProceedings of 2008 3rd International Conference on Intelligent System and Knowledge Engineering, ISKE 2008 - Xiamen
    Duration: 17 Nov 200819 Nov 2008

    Publication series

    NameProceedings of 2008 3rd International Conference on Intelligent System and Knowledge Engineering, ISKE 2008

    Conference

    ConferenceProceedings of 2008 3rd International Conference on Intelligent System and Knowledge Engineering, ISKE 2008
    Country/TerritoryChina
    CityXiamen
    Period2008-11-172008-11-19

    ASJC Scopus subject areas

    • Hardware and Architecture
    • Control and Systems Engineering
    • Electrical and Electronic Engineering

    Cite this