Abstract

Pathfinding algorithms have played a pivotal role in several fields, ranging from video game features such as maps to transportation and geographic information systems used in everyday life. In this study, four of the most prevalent pathfinding optimization algorithms are analyzed, juxtaposed, and tested, namely Dijkstra’s algorithm, A-star’s algorithm, Bellman-Ford’s algorithm, and Floyd-Warshall’s algorithm. The goal is to evaluate their performance, efficiency, and suitability on the campus of the College of Wooster to create a visual aid that students can use to become more efficient in their daily travels. Each algorithm will be implemented and tested on sparse graphs that vary in node densities and obstacle configurations. Metrics such as time complexity, optimal paths, and nodes explored & visited will be used for evaluation. Additionally, a custom campus navigation application was developed using C++ and SFML to visualize algorithms’ behaviours in a practical context. The results determine the best algorithm in the given context, highlighting trade-offs between efficiency and accuracy

Advisor

Palmer, Daniel

Second Advisor

Guarnera, Heather

Department

Computer Science

Disciplines

Computer Sciences | Graphics and Human Computer Interfaces | Numerical Analysis and Scientific Computing | Theory and Algorithms

Keywords

Dijktstra, A-star, Bellman-Ford, Floyd-Warshall, Optimal, Pathfinding, Shortest Path, Efficiency, Implementation, Node, Edge, Graph

Publication Date

2025

Degree Granted

Bachelor of Arts

Document Type

Senior Independent Study Thesis

Download

Share

COinS
 

© Copyright 2025 Paa Kweku H. Cato