Comparative Analysis of Floyd Warshall and Dijkstras Algorithm using Opencl
Asad Mohammad, Vikram V. Garg · International Journal of Computer Applications · 2015
Shortest path algorithms finds applications in large real world domains.All pair shortest path (APSP) and single source shortest path (SSSP) both have their special applications domains.All though every SSSP can be applied for all vertices to calculate APSP.But APSP cant.In this paper heterogeneous implementation of Floyd warshalls algorithm and Dijkstra's algorithm is compared on dense graphs have positive edge weights ranging from 1 to 10.It is found that Dijkstra's algorithm is better than Floyd warshall algorithm in sequencial implementation.But as there is less parallelism identified in dijkstra algorithm as compared to parallel to parallel FW gives less execution time as compared to Dijkstra's.