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

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.