Efficiently navigating a library's vast collection of books can be challenging, especially in large academic libraries. To enhance the user experience and streamline the search process, I developed a pathfinding program for the College of New Jersey's library app, which aims to provide the optimal path between a user's starting location and their desired book within the library.

The first step in developing the program was to utilize graph theory to abstract the library floor plan/environment in a way that could be understood by the algorithm. To accomplish this, a graph was drawn on top of a pre-existing floorplan by marking all intersections of realistic paths a human may take, taking into consideration obstacles such as walls, pillars, tables, and balconies. Each intersection was considered as a vertex, and an edge was defined as two adjacent vertices. Once the floor plan was abstracted into a graph, the algorithm to find the shortest path between two vertices was implemented. After considering various algorithms such as BFS, DFS, and A*, I selected Dijkstra's algorithm due to its optimality and uninformed nature. The algorithm was implemented in C, a common programming language, to ensure its ease of comprehension. To evaluate the efficiency of the path finding program, experiments were conducted to measure the execution time of Dijkstra's algorithm on various-sized graphs. The time taken to find the shortest path between two vertices was recorded and analyzed to evaluate the performance of the program. Additionally, the accuracy of the program was tested by comparing the paths generated by the program with the paths taken by actual humans in the library environment.

The program produced correct results for the first floor of the library. After running the program 10,000 times on floor 1's data with randomly selected start and end vertices, the average time spent finding the correct path was .000483 seconds, indicating its efficiency and capability to quickly provide the necessary information to users. Preliminary testing on floor 2 suggests that the program is effective, despite some human error in the creation of the input files for the program, leading to discrepancies in the output. It is important to note that this error does not reflect on the program's functionality, and further testing will be conducted to ensure accurate results.

You can view the source code here.