A Comparative Study on Analysis of Various Shortest Path Algorithms on GPU using OPENCL | Zendy

Umesh Nayak | Zendy; Rajeev Pandey | Zendy; Uday Chourasia | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Comparative Study on Analysis of Various Shortest Path Algorithms on GPU using OPENCL

Author(s) -

Umesh Nayak,

Rajeev Pandey,

Uday Chourasia

Publication year - 2018

Publication title -

international journal of computer applications

Language(s) - English

Resource type - Journals

ISSN - 0975-8887

DOI - 10.5120/ijca2018916948

Subject(s) - computer science , shortest path problem , path (computing) , algorithm , computer graphics (images) , parallel computing , computational science , theoretical computer science , programming language , graph

Finding shortest path for various applications is important in various domains. But to provide result for complex graphs in real time is a challenging task. So in this paper four shortest path algorithms namely Dijkstra’s algorithm, Floyd Warshall, Bellman Ford and Jhonsons algorithm are studied and analyzed to detect parallelism in them and the parallelized version of all three is implemented using parallel computing framework OpenCL. It is found that Bellman Ford and Floyd Warshall contains fine grained parallelism while Jhonsons has less parallelism.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research