How I Used BFS to Find the Shortest Route in Tehran Metro with React

When I started building Metrino, a Tehran Metro route planner, I had a simple question:

«How can I find the shortest route between two metro stations?»

The UI was only one part of the problem. Underneath the map and station selectors, I needed a way to represent the Tehran Metro network and calculate a route between two stations.

The solution was to model the metro network as a graph and use Breadth-First Search (BFS) to find the shortest path.

🚇 Turning the Metro Into a Graph

Instead of thinking about the metro as a visual map, I represented it as a graph.

Each station is a node.

Each connection between two stations is an edge.

For example:

Station A
│
▼
Station B ─── Station C
│
▼
Station D

In my data model, each station contains a list of connected stations.

This means I can ask:

«"Which stations can I reach directly from this station?"»

The application builds a bidirectional adjacency map when the metro data is initialized:

const adj = new Map>();

this._stations.forEach((s) => {
if (!adj.has(s.id)) adj.set(s.id, new Set());

s.connectedStationIds.forEach((nid) => {
adj.get(s.id)!.add(nid);

// Add reverse direction
if (!adj.has(nid)) adj.set(nid, new Set());
adj.get(nid)!.add(s.id);

});
});

This gives the route finder a structure that is easy to traverse.

🧭 Why BFS?

For the first version of the route planner, I wanted to minimize the number of station-to-station hops.

That's where BFS works well.

Breadth-First Search explores a graph level by level:

Start
│
├── A
├── B
└── C
│
├── D
├── E
└── F

It first explores the stations closest to the starting station, then moves to the next level.

Because every connection has the same cost in this version of the problem, the first route BFS finds to the destination is the route with the fewest hops.

💻 The Actual BFS Implementation

Here is the actual "findPath" implementation from Metrino:

findPath(fromId: string, toId: string): string[] | null {
if (fromId === toId) return [fromId];

const visited = new Set();

const queue: Array<{ id: string; path: string[] }> = [
{ id: fromId, path: [fromId] },
];

visited.add(fromId);

while (queue.length > 0) {
const { id, path } = queue.shift()!;

const neighbors = this._adjacency.get(id) ?? [];

for (const neighbor of neighbors) {
  if (neighbor === toId) {
    return [...path, neighbor];
  }

  if (!visited.has(neighbor)) {
    visited.add(neighbor);

    queue.push({
      id: neighbor,
      path: [...path, neighbor],
    });
  }
}

}

return null;
}

Let's break it down.

1. Handle the same station

if (fromId === toId) return [fromId];

If the origin and destination are the same station, there is nothing to calculate.

1. Keep track of visited stations

const visited = new Set();

Without this, the algorithm could keep visiting the same stations again and again.

I immediately mark the starting station as visited:

visited.add(fromId);

1. Create the queue

const queue: Array<{ id: string; path: string[] }> = [
{ id: fromId, path: [fromId] },
];

The queue contains the station we're currently exploring and the path that led to it.

For example:

{
id: "station-b",
path: ["station-a", "station-b"]
}

This makes it easy to return the complete route once we reach the destination.

1. Explore the graph

while (queue.length > 0) {

As long as there are stations waiting to be explored, BFS continues.

We remove the first item from the queue:

const { id, path } = queue.shift()!;

Then get all directly connected stations:

const neighbors = this._adjacency.get(id) ?? [];

1. Check the destination

if (neighbor === toId) {
return [...path, neighbor];
}

As soon as BFS reaches the destination, we return the complete station sequence.

For example:

Station A
↓
Station B
↓
Station C
↓
Station D

The returned result would look like:

[
"station-a",
"station-b",
"station-c",
"station-d"
]

1. Add unvisited stations to the queue

if (!visited.has(neighbor)) {
visited.add(neighbor);

queue.push({
id: neighbor,
path: [...path, neighbor],
});
}

This is what allows BFS to move through the network level by level.

🔄 What About Line Transfers?

Finding the shortest path is only part of the problem.

Tehran Metro has multiple lines, so after finding the station path, I also need to determine where passengers change lines.

The route service looks at consecutive stations and finds their shared line:

private _getCommonLine(a: Station, b: Station): number | null {
for (const line of a.lines) {
if (b.lines.includes(line)) return line;
}

return null;
}

Then the route builder can detect when the route changes from one line to another.

For example:

Line 1
│
│
▼
Station A
│
▼
Transfer Station
│
│
▼
Line 4
│
▼
Station B

The transfer is recorded separately from the BFS path.

⏱️ Estimating Travel Time

BFS gives me the route, but it doesn't tell me how long the journey will take.

So after finding the path, Metrino calculates an estimated travel time using:

• approximate distance between stations
• an average train speed
• station dwell time
• transfer time

The current implementation uses:

const TRANSFER_PENALTY_MIN = 3;
const STATION_DWELL_SEC = 30;
const AVG_SPEED_KMH = 40;

The total estimate is then built from these values.

These are estimates, not official Tehran Metro schedules.

🧩 Separating the Algorithm From the UI

One thing I wanted to avoid was putting route calculation directly inside React components.

Instead, I separated the responsibilities:

React UI
↓
MetroRouteService
↓
MetroDataService
↓
Metro Graph / Metro Data

"MetroDataService" handles the station, line, connection, and adjacency data.

"MetroRouteService" takes the resulting path and turns it into a complete route containing:

• origin
• destination
• station sequence
• segments
• transfers
• distance
• estimated time

This separation makes the UI much easier to work with.

📈 What's Next?

BFS was a good starting point because the first version of Metrino only needed to minimize the number of station hops.

But the real-world "best route" isn't always the route with the fewest stations.

For example, a slightly longer route might be better if it has fewer transfers or takes less time.

That's why one of the next improvements I'd like to explore is weighted pathfinding, using algorithms such as Dijkstra's algorithm or A*.

The goal would be to consider things like:

Station count

• Travel time
• Transfer penalties

instead of only counting station hops.

🚀 What I Learned

The biggest lesson from building this feature was that many problems that look like UI problems are actually data structure and algorithm problems.

The metro map is a UI.

But underneath that UI, it's a graph.

Once I represented the metro network as a graph, route calculation became much easier to reason about.

BFS gave me a simple and reliable starting point, and it was enough to power the first version of the route planner.

🚇 Try Metrino

I built Metrino as a Persian-first Tehran Metro web application with React, TypeScript and Vite.

Live Demo: https://metrino.vercel.app/

GitHub: https://github.com/HamedFarazi/metroapp

The project is open source, and I'm continuing to improve the routing, maps, PWA experience, and accessibility.

Thanks for reading 💫