PathFinder: A Comparative Analysis of Graph Traversal Algorithms

📌 Executive Summary

PathFinder is a dual-environment framework designed to analyze and visualize the efficiency of various pathfinding algorithms. The project consists of a High-Performance Python Engine for raw algorithmic benchmarking and an Interactive Web Dashboard for real-time spatial visualization.

By comparing Uninformed Search (BFS, DFS) against Informed Search (A*, Dijkstra), this project demonstrates how heuristic functions significantly optimize computational overhead in complex grid-based environments.

---

🔬 Core Algorithms & Theoretical Analysis

The project evaluates four fundamental approaches to the Shortest Path Problem on a 2D coordinate space $G = (V, E)$.

Algorithm	Strategy	Time Complexity	Optimality
BFS	Layer-by-layer exploration	$O(V + E)$	Yes (Unweighted)
DFS	Recursive branch exploration	$O(V + E)$	No
Dijkstra	Greedy cost-minimization	$O(E + V \log V)$	Yes
A Search*	Heuristic-guided optimization	$O(E)$ (Approx)	Yes (Admissible)

Heuristic Optimization in A*

For the A* implementation, we utilize the Manhattan Distance formula to calculate the estimated cost $h(n)$: $$h(n) = |x_{target} - x_{n}| + |y_{target} - y_{n}|$$ This heuristic ensures that the algorithm remains admissible, meaning it never overestimates the cost to reach the goal, thus guaranteeing an optimal path while expanding fewer nodes than Dijkstra.

---

🛠 Project Architecture

The repository is structured to separate data analysis from user interaction:

pathfinding-analysis/
├── results/              # Output of Python benchmarks
│   ├── metrics.txt       # Time (ms) and Nodes Expanded data
│   └── paths.txt         # Coordinate-level path logs
├── src/                  # Backend Python Engine
│   ├── search.py         # Algorithmic implementations
│   ├── main.py           # Benchmark execution script
│   └── grid.py           # Graph representation logic
├── index.html            # Web Visualizer (Root for deployment)
├── style.css             # Glassmorphism UI styling
└── script.js             # Asynchronous DOM-based search logic

Algorithm       Path Length    Nodes Expanded    Time (ms)
----------------------------------------------------------
BFS             18             55                0.1961 ms
DFS             34             35                0.1109 ms
A* (Manhattan)  18             52                0.2311 ms