The Floyd-Warshall algorithm is a widely utilized graph-based technique designed to address the all-pairs shortest path problem. However, its cubic time complexity $O\left(n^{3}\right)$ creates performance bottlenecks when applied to large graphs, especially in sequential execution. This paper explores the use of Intel oneAPI’s Data Parallel C++ (DPC++) programming model to optimize the performance of the Floyd-Warshall algorithm through parallel processing. A comparative performance analysis between sequential and parallel implementations on an Intel Xeon(R) CPU highlights up to a $43 \%$ improvement in execution time for graphs with 800 nodes. The results underscore the potential of parallel computing in significantly reducing computational time for large-scale graph algorithms.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Performance Analysis of Floyd-Warshall Algorithm: Sequential and Parallel Execution Using Intel oneAPI


    Contributors:


    Publication date :

    2024-11-06


    Size :

    432642 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Floyd J. Lupton

    Online Contents | 1995



    A Parallel CFD Algorithm on the Intel PARAGON[TM] Computer

    Tsai, M. C. | British Library Conference Proceedings | 1993