This repository contains the complete computational framework and analytical pipeline used to evaluate Shortest Path Problem (SSP) algorithms within the unique urban morphology of the Lucknow district. By leveraging a high-fidelity dataset of 302,066 nodes, this research benchmarks the performance of Uninformed (Dijkstra) vs. Informed (A)* search algorithms using a Haversine-based admissible heuristic.
- Mean State-Space Reduction: 78.13%
- Computational Efficiency: A* visits ~1,393 nodes/km vs. Dijkstra’s ~6,396 nodes/km.
- Topological Discovery: Identification of the "Gomti Riverine Bottleneck Paradox" and the "Cantonment Regularity Effect."
The detailed theoretical findings, mathematical proofs, and exhaustive geospatial analysis are available in the accompanying paper.
- Language: C++17 (Optimized for high-performance graph traversal)
- Data Parsing:
Libosmium(Fast OSM PBF binary handling) - Analytics: Python 3.10 (Pandas, Seaborn, Scipy)
- Heuristic: Spherical Haversine Formula (Earth Curvature Admissible)
/src: C++ source code for the pathfinding engine./data: Sample metadata and coordinate bounding boxes./analysis: Python scripts (main.py) used for generating statistical figures./plots: High-resolution regression and density visualizations.
No credit goes to school (Army Public School Sardar Patel Marg, Lucknow). This research was conducted entirely through independent self-study and rigorous empirical evaluation by the author.
© 2026 Prateek Tiwari. All Rights Reserved.
- Educational Usage: Permission is granted for individual researchers/students for strictly non-commercial, personal study.
- Institutional Prohibition: Any school, university, or corporate entity is strictly prohibited from using, citing, or distributing this work for promotional, commercial, or institutional accreditation purposes without express written authorization.
- No Institutional Attribution: No academic institution shall claim credit for the production, supervision, or results of this research.
For inquiries regarding the methodology or permission for extended usage:
- Researcher: Prateek Tiwari
- Email: prateektiwari258@gmail.com
- Location: Lucknow, Uttar Pradesh, India