A* and Dijkstra’s algorithm simultaneously on NVIDIA  GPU using CUDA C++

Shishir Govinda M; Thrisha V S

A* and Dijkstra’s algorithm simultaneously on NVIDIA GPU using CUDA C++

Authors: Shishir Govinda M, Thrisha V S

Unique Paper ID: 169055
Volume: 11
Issue: 6
PageNo: 236-244

Keywords: CUDA C++ A* Dijkstra GPU CPU Path finding.

Abstract:
A* algorithms is the best known path finding algorithm which is guided by a heuristic function to reach the goal node. Dijkstra’s path finding algorithm works on greedy method i.e., it checks all the neighbouring nodes and is not guided by a heuristic function. In this paper, we try to achieve a much faster way of computing the path by combining both A* and Dijkstra’s algorithm, where in we will be using A* algorithm from the start node and Dijkstra’s algorithm from the goal node and at the point of intersection we will have our path. To further increase the speed of computation we will be making use of Nvidia’s GPU computation via CUDA C++. We will also see the computational speed difference between serial CPU computation and parallel GPU calculation and comparing the results learned with Amdahl’s Law in Parallel Computing. We will also look at some of the hindrances faced while enabling computation with Nvidia GPU using CUDA C++, which are non-existent with GPU computation.

Download article

email to a friend

Cite This Article

ISSN: 2349-6002
Volume: 11
Issue: 6
PageNo: 236-244

A* and Dijkstra’s algorithm simultaneously on NVIDIA GPU using CUDA C++

Available:https://ijirt.org/Article?manuscript=169055

Impact Factor
8.01 (Year 2024)

UGC Approved
Journal no 47859

Join Our IPN

IJIRT Partner Network

Submit your research paper and those of your network (friends, colleagues, or peers) through your IPN account, and receive 800 INR for each paper that gets published.

Join Now