A COMPARISON OF PARALLEL IMPLEMENTATIONS OF PATHFINDING ALGORITHMS

Abstract

Pathfinding algorithms are in constant use today – be it for generating driving directions or maintaining the routing tables that are used for routing traffic around the Internet. As would be expected, a given algorithm’s performance varies depending upon both the type and the scale of the application. Additionally, the use of parallel computing techniques may or may not decrease the runtime for a given problem. This thesis examines three commonly used pathfinding algorithms – Dijkstra, Bellman-Ford, and Floyd-Warshall – and seeks to illustrate their strengths and weaknesses when analyzing graphs that range from small and sparse to large and dense in various parallel computing environments. As well, focus is given to the use of Graphics Processing Units (GPUs) as parallel computing devices themselves and the consequential reduction in the amount of hardware necessary for a given task.