abduldattijo/abuja-dijkstra-astar

Companion code for "How Dijkstra and A Star Search a Map, Step by Step": a hand traceable graph, then the same algorithms on a real 160,933 node Abuja, Nigeria road network. # Abuja Dijkstra and A Star Routing A hand traceable implementation of Dijkstra's algorithm and A star search, run first on two small invented graphs and then on a real 160,933 node road network built from OpenStreetMap data for Abuja, Nigeria. This repo is the companion code for the article *The Algorithm Dijkstra Invented Over Coffee in Twenty Minutes*. ## What the code does 1. `toy_example.py` traces both algorithms by hand through two small graphs, one with a decoy branch A star can skip outright, one with two routes that stay close in cost until the very end, and writes the full step-by-step trace for each. 2. `fetch_osm_data.py` downloads every mapped road inside a fixed Abuja bounding box from the Overpass API. 3. `build_graph.py` converts the raw extract into a weighted graph and keeps only its largest connected component. 4. `run_experiment.py` runs Dijkstra and A star from the airport to three real destinations, timing each run and counting nodes examined. 5. `speed_weighted_experiment.py` reruns the same routes weighting each edge by an assumed travel speed instead of raw distance, and compares the resulting route against the distance shortest one. 6. `make_figures.py` turns the JSON output of the scripts above into every image used in the article. ## Setup ```bash python -m venv .venv source .venv/bin/activate pip install -r code/requirements.txt ``` No API key is required. The Overpass API is queried through its public, unauthenticated endpoint. Generating images additionally needs `rsvg-convert` on your PATH, part of the librsvg package (`brew install librsvg` on a Mac, `apt install librsvg2-bin` on Debian or Ubuntu). ## Run everything ```bash python code/toy_example.py python code/fetch_osm_data.py python code/build_graph.py python code/run_experiment.py python code/speed_weighted_experiment.py python code/make_figures.py ``` Run in this order from the repo root. `fetch_osm_data.py` downloads a few tens of megabytes and can take a couple of …