Route Planning on the Delhi Metro Network: A Benchmark Study of Shortest-Path Algorithms (Python)

Route Planning on the Delhi Metro Network is a benchmarks-driven algorithms study written for the University of Delhi UGCF dissertation track (Semesters 7 and 8). Instead of testing shortest-path algorithms on the six-node toy graphs found in textbooks, it builds a weighted graph of the real Delhi Metro — 10 colour-coded lines, roughly 243 unique stations (271 station entries counting interchanges) and about 374 km of route — and measures how the classic trio Dijkstra, Bellman-Ford and A* actually behaves on it.

The study does four things. First, it curates a machine-readable station dataset from Wikipedia's line-wise station lists, cross-checked against the Delhi Metro Rail Corporation's official station list, with every source documented. Second, it constructs the adjacency structure correctly: consecutive stations on a line become edges, interchange stations get transfer edges, and edge weights model travel time rather than hop count. Third, it implements all three algorithms from scratch in Python and validates each one against the NetworkX reference implementation (an industry-standard library used only for cross-checking), so correctness is never assumed. Fourth, it runs a reproducible benchmark protocol — warm-up runs, fixed query sets and repeated trials timed with time.perf_counter — and reports runtimes, expanded-node counts and route quality side by side.

A small command-line tool prints itineraries for real journeys such as Rithala to Botanical Garden, and matplotlib figures (another industry-standard extra) draw the network and the timing results. Everything runs offline on an ordinary laptop.

A metro commuter choosing between two routes faces a real trade-off: the route with fewer interchanges may be longer in distance, and the route with fewer stops may need two line changes. Every route planner resolves this with shortest-path algorithms, but the algorithm behind the answer is never shown, and the weights that decide what "shortest" means are hidden. Meanwhile, computer-science students learn Dijkstra, Bellman-Ford and A* only on textbook graphs of a few nodes, where no algorithm shows any measurable advantage and interchange costs never arise.

There is no measured, reproducible evidence for the questions this dissertation asks: by how much does Bellman-Ford actually trail Dijkstra on a real transit network? Does the A* heuristic genuinely pay for its bookkeeping on a sparse, near-planar metro graph? And does interchange-aware weighting change which route counts as "shortest"? This study builds the dataset, the from-scratch implementations and the benchmark protocol needed to answer those questions with numbers instead of folklore, on a network every Delhi student knows first-hand.

Abstract

This dissertation benchmarks three classic shortest-path algorithms — Dijkstra's algorithm, the Bellman-Ford algorithm and A* search — on a weighted graph of the Delhi Metro built entirely from public data. The graph has about 243 unique stations across 10 lines, with interchanges modelled as explicit transfer edges. All three algorithms are implemented from scratch in Python, validated against NetworkX reference results on every ordered station pair, and timed on fixed query sets under a documented protocol. The study reports measured runtimes, memory use and route quality, and analyses when each algorithm is the right choice for transit routing.

Introduction

Route planning looks solved: mobile apps answer "Rithala to Botanical Garden?" in a second. But exactly how they answer it is invisible, and a B.Sc. curriculum teaches Dijkstra, Bellman-Ford and A* on tiny classroom graphs where every algorithm is instant and every route is obvious. The learning gap is real: students never see how graph size, edge density, weight design and interchange handling change behaviour. This study closes that gap by treating the Delhi Metro as a serious, verifiable dataset — large enough to produce measurable differences between algorithms, small enough to check by hand.

Existing systems and the gap

• Official and commercial planners (the DMRC app and third-party transit apps) are closed products: users cannot inspect the graph, the weights or the algorithm, and none publish benchmarks.
• Textbook treatments run algorithms on graphs of five to ten nodes, so running-time differences are unmeasurable and interchange modelling never appears.
• Typical student projects either hard-code a small sample of stations or simply call a library, which is fatal in a viva when the examiner asks what a binary heap actually does.
• The gap: no measured, reproducible, from-scratch comparison of these three algorithms on a real Indian metro network with interchange-aware weights.

Proposed study

Build the station graph in three verified weight models — pure hop count, distance-based travel time, and travel time plus a fixed interchange penalty. Implement Dijkstra with a binary heap, Bellman-Ford with early exit, and A* with a haversine-based heuristic, all from scratch. Prove correctness against NetworkX on all ordered station pairs under every weight model, then time all algorithms on three fixed query sets: same-line journeys, one-interchange journeys and terminal-to-terminal worst cases. Analyse the results and present them with fully reproducible scripts.

Feasibility

• Technical: the entire study runs on a student laptop; the largest computation (all-pairs Dijkstra over 243 nodes) finishes in seconds. All data is public and downloadable.
• Economic: zero cost — no paid APIs, no cloud credits, only free open-source tools.
• Operational: the 24-week UGCF dissertation window (6 credits per semester) comfortably fits data collection, implementation, experiments and writing, and the scheme's monthly progress reports keep the work visible to the supervisor throughout.

In scope

• The static Delhi Metro network: all 10 colour-coded lines and roughly 243 unique stations as publicly listed (271 station entries counting interchanges).
• Single-source, single-destination shortest paths under three weight models; interchanges modelled as transfer edges with a configurable penalty.
• From-scratch implementations of Dijkstra (binary heap), Bellman-Ford (early exit) and A* (haversine heuristic); NetworkX used strictly as a correctness reference, never inside the measured code paths.
• Benchmarking on three fixed query sets (same-line, one-interchange, terminal-to-terminal) with warm-up runs and 30 timed repetitions per query.
• A CLI route demo and matplotlib figures of the network and the results.

Out of scope (and why)

• Timetable-aware routing: real train frequencies, dwell times and first/last trains are scheduling data, not graph structure, and would drown the algorithmic question.
• Live disruptions, crowd levels and holiday timetables; the study models a typical network, not a real-time feed.
• Fares, ticketing and first/last-mile integration.
• Other cities in the main study — though the pipeline is written so that a Mumbai or Kolkata station file can replace the input with minimal edits.

The study follows an experimental benchmarking research design mapped onto the two-semester UGCF dissertation: Semester 7 builds the artefact (data, graph, implementations) and Semester 8 runs the experiments and writes the dissertation. The design has one treatment (the algorithm), three controlled conditions (the weight models), one fixed workload (three query sets) and repeated measurement — the standard structure for a fair runtime comparison. Monthly progress reports to the supervisor are a scheme requirement and are used as checkpoints at the end of every phase.

Testing approach: pytest unit tests cover boundaries (source equals destination, adjacent stations, terminal-to-terminal) and hand-verified known routes; a full-network cross-check asserts that every from-scratch route matches NetworkX's Dijkstra under the same weights. Benchmark hygiene: one machine, no background load, warm-up excluded from statistics, median and 95th percentile reported alongside the mean.

The study is a pipeline of small, independently testable scripts rather than an application. Raw sources flow through a curation step into a versioned stations.csv; a builder turns it into adjacency lists under each weight model; the algorithms module consumes the graph; the harness times it; notebooks analyse the output. Each stage writes a file, so any stage can be re-run without redoing the earlier ones, and every artefact in the dissertation regenerates from the raw data with one command chain.

flowchart TD
  W["Wikipedia line-wise station lists"] --> C["stations.csv curation script"]
  D["DMRC official station list"] --> C
  C --> V["Verification: per-line counts and interchange flags"]
  V --> G["build_graph.py: adjacency lists with weights"]
  G --> M1["Weight model 1: hop count"]
  G --> M2["Weight model 2: distance-based travel time"]
  G --> M3["Weight model 3: travel time plus interchange penalty"]
  M1 --> Q["Query sets: same-line, one-change, terminal-to-terminal"]
  M2 --> Q
  M3 --> Q
  Q --> A["From-scratch Dijkstra, Bellman-Ford, A-star"]
  N["NetworkX reference implementations"] --> A
  A --> T["pytest correctness suite"]
  A --> B["benchmark.py: warm-up, 30 repeats, perf_counter"]
  B --> R["results.csv"]
  R --> P["Analysis notebooks and matplotlib figures"]
  P --> F["Dissertation chapters and defence deck"]
  A --> U["route.py CLI itinerary demo"]

The graph keeps one node per station per line, joined by transfer edges at interchange stations, which is what makes the interchange penalty expressible as an ordinary edge weight:

flowchart LR
  subgraph RedLine["Red Line"]
    NSP["Netaji Subhash Place (R)"] --- KG_R["Kashmere Gate (R)"]
  end
  subgraph YellowLine["Yellow Line"]
    KG_Y["Kashmere Gate (Y)"] --- NDLS["New Delhi"]
  end
  KG_R -. "transfer edge, weight 5 min" .- KG_Y

Design decisions worth defending in the viva: adjacency lists over matrices (the metro graph is very sparse, about two same-line edges per node); a binary heap for Dijkstra to get the standard O((V+E) log V) bound; an early exit for Bellman-Ford when a pass changes no distance; and an admissible, consistent haversine heuristic for A* so that no closed node ever needs reopening.

• Time-dependent weights: replace constant weights with headway-based waiting times at interchanges, turning the study into schedule-aware routing.
• Faster algorithms: bidirectional Dijkstra and Contraction Hierarchies benchmarked the same way make an excellent follow-up chapter.
• Other networks: the pipeline accepts any station table — Mumbai, Kolkata or the Namo Bharat RRTS drop in with a new CSV.
• Open GTFS: if a metro GTFS feed appears on an open data portal, ingest it directly and retire the manual curation step.
• Uncertainty: report route-time confidence intervals instead of single numbers, using the variance already captured across benchmark repetitions.