The week's pick
Reseach Article
Comparative Analysis of Floyd Warshall and Dijkstras Algorithm using Opencl
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 128 - Number 17 |
| Year of Publication: 2015 |
| Authors: Asad Mohammad, Vikram Garg |
10.5120/ijca2015906305
|
Asad Mohammad, Vikram Garg . Comparative Analysis of Floyd Warshall and Dijkstras Algorithm using Opencl. International Journal of Computer Applications. 128, 17 ( October 2015), 4-6. DOI=10.5120/ijca2015906305
Abstract
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.
References
- R. Bellman. On a routing problem. Quarterly of Applied Mathematics 16:87-90,1958.
- Yefim Dinitz , Rotem Itzhak , Hybrid Bellman-Ford-Dijkstra Algorithm.
- Aydın Buluc , John R. Gilbert and Ceren Budak , “Solving Path Problems on the GPU” , Journal Parallel Computing Volume 36 Issue 5-6, June,2010 Pages 241-253.
- Andrew Davidson , Sean Baxter, Michael Garland , John D. Owens , “Work-Efficient Parallel GPU Methods for Single-Source Shortest Path “ in International Parallel and Distributed Processing Symposium, 2014
- Owens J.D., Davis, Houston, M., Luebke, D., Green, S., “GPU Computing”, in: Proceedings of the IEEE, Volume: 96 , Issue: 5 , 2008.
- A. Munshi, B. R. Gaster, T.G. Mattson, J. Fung, D. Ginsburg, “OpenCL Programming Guide”, Addison-Wesley pub., 2011.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition. The MIT Press, Sep. 2001.
- Kumar, S.; Misra, A.; Tomar, R.S. ,”A modified parallel approach to Single Source Shortest Path Problem for massively dense graphs using CUDA” in Computer and Communication Technology (ICCCT), 2011 2nd International Conference on , vol., no., pp.635,639, 15-17 Sept. 2011.
- Atul Khanna, John Zinky , “The Revised ARPANET Routing Metric”, in 1969 ACM.
- Hristo Djidjev and Sunil Thulasidasan,Guillaume Chapuis, Rumen Andonov, and Dominique Lavenier "Efficient Multi-GPU Computation of All-Pairs Shortest Paths" in 2014 IEEE 28th International Parallel & Distributed Processing Symposium.
Index Terms
Keywords