Optimal Route Planning in Delhi Metro Using Graph Algorithms

Anyone who has travelled in the Delhi Metro knows an interesting fact:

The shortest route is not always the best route.

A path with fewer stations can feel worse if it requires multiple interchanges.

A slightly longer route can feel easier if you stay on the same line throughout.

This reveals an important idea:

“Optimal” in transportation networks is not just distance.

It depends on multiple human-centric factors:

• Number of interchanges
• Total stations travelled
• Ease of navigation and reliability

This project builds a Delhi Metro Route Finder using graph theory and classical shortest-path algorithms that automatically computes the most practical route using real metro data stored in JSON.

The key challenge is not the algorithm — it is the correct modeling of the problem.

Modeling the Metro as a Graph

A metro network naturally maps to a graph:

• Vertices (nodes) → Stations
• Edges → Direct connections between stations

This is the standard abstraction used in transportation networks.

However, this station-only graph is incomplete.

Why?

Because certain stations belong to multiple lines (e.g., Kashmere Gate, Rajiv Chowk).

A passenger’s experience depends not only on the station, but also on which line they are currently on.

A simple graph cannot represent the cost of changing lines.

So we need a richer representation.

Station–Line State Expansion (Core Theoretical Idea)

Instead of representing a node as just a station:

Rajiv Chowk

We represent it as a state:

(Rajiv Chowk, Yellow Line)  
(Rajiv Chowk, Blue Line)

This technique is known as state expansion in graph theory.

Now the graph can represent:

• The current line of the passenger
• When a line change happens
• How to assign a cost to that change

This transforms a simple graph into a state graph, which is much more expressive and realistic.

This single modeling decision allows classical algorithms to solve a multi-criteria real-world problem.

Data-Driven Design Using JSON

All metro data is stored in dmrc.json.

This file describes:

• Lines passing through each station
• Previous and next stations on each line
• Interchange possibilities

This separation of data from algorithms provides:

• Maintainability (new stations → only JSON changes)
• Clean algorithmic code
• Reusability across platforms

The JSON becomes the single source of truth for the network.

Building the State Graph

From the JSON file, we build an adjacency list where each node is:

station | line

Two types of edges are created:

1) Line Continuity Edges

Between consecutive stations on the same line.

2) Interchange Edges

Between the same station across different lines.

The metro system is now a weighted state graph rather than a simple station graph.

Algorithm 1 — Minimum Interchange Route (Modified Dijkstra)

The optimization goal is lexicographic:

1. Minimize interchanges
2. If equal, minimize stations

This cannot be solved by BFS or a standard shortest path.

So we adapt Dijkstra’s algorithm.

Each state maintains a cost:

(interchanges, stations\_travelled)

The priority queue compares costs lexicographically:

(0,15) < (1,5)

This ensures that fewer interchanges are always preferred, even if the path has more stations.

Edge Relaxation Logic

When moving between states:

• If line changes → interchanges + 1
• Always → stations + 1

This encodes human discomfort directly into the graph.

Algorithm 2 — Minimum Stations Route (BFS)

We also implement BFS to compute:

Path with the fewest stations, ignoring interchange cost.

Why BFS works here:

• Every edge represents one station hop
• BFS guarantees minimum hops

This serves as a baseline comparison.

Automatic Route Selection Strategy

The system automatically selects the best route using:

1. Minimum interchanges
2. If tie → minimum stations

This mirrors real passenger preferences more closely than pure distance minimization.

Path Reconstruction

During traversal, each visited state stores its parent.

After reaching the destination, we backtrack:

destination → ... → source

Then reverse the sequence to produce the final route.

Time and Space Complexity

Let:

• V = number of (station, line) states
• E = number of connections

Even large metro networks are handled efficiently.

Why This Design is Theoretically Strong

✔ Uses state expansion, a classical graph modeling technique

✔ Converts a multi-criteria problem into a shortest-path problem

✔ Separates data and logic cleanly

✔ Matches human commuter behavior

✔ Demonstrates practical use of Dijkstra and BFS

📂 Metro Dataset (JSON)

This repository contains the complete structured representation of the Delhi Metro network:

• Stations
• Lines
• Previous/next connections
• Interchange information

This acts as the single source of truth for the entire system and can be reused across languages or platforms.

🔗 Dataset Repository: <DATASET_GITHUB_LINK>

⚙️ Graph Algorithms and Route Finder (C++)

This repository contains the complete implementation of:

• Graph construction from JSON
• State expansion modeling
• Modified Dijkstra’s algorithm (minimum interchanges)
• BFS algorithm (minimum stations)
• Path reconstruction and CLI interaction

The code demonstrates how classical graph algorithms can be adapted to solve a real-world transportation problem through proper modeling.

🔗 Algorithms Repository: <ALGO_GITHUB_LINK>

Conclusion

This small project demonstrates an important lesson:

The power of graph algorithms lies not only in the algorithm, but in how the problem is modeled.

By expanding stations into station–line states and applying classical algorithms like Dijkstra and BFS, we solve a real-world transportation problem elegantly and efficiently.

This system can be extended further with:

• Fare estimation
• Travel time prediction
• Crowd-aware routing
• Real-time metro updates

A clear example of how good modeling + classical algorithms = practical system design.