Solution: Bus Routes

Statement

You are given an array, routes, representing bus routes where routes[i] is a bus route that the $i^{th}$ bus repeats forever. Every route contains one or more stations. You have also been given the source station, src, and a destination station, des. Return the minimum number of buses someone must take to travel from src to dest, or return -1 if there is no route.

Constraints:

• $1 \le$ routes.length $\le 500$
• $1 \le$ routes[i].length $\le 10^3$
• $0 \le$ routes[i][j] $< 10^5$
• $0 \le$ src, dest $< 10^5$

Solution

The solution starts by creating an adjacency list that maps each station to the buses that travel through that station. This is done by iterating through routes and, for each route, adding the route's index to the adjacency list for each station in that route.

Next, we use the BFS algorithm to find a path from src to dest using the minimum number of buses since BFS always finds the shortest path in an unweighted graph. The BFS algorithm is implemented using a queue that stores the current station and the number of buses taken to reach that station. The queue is initialized with src and a bus count of 0.

Then, we repeatedly dequeue the next station from the queue, and if it is equal to the dest, we return the number of buses. Otherwise, we iterate through the buses that travel through the current station and, for each unvisited bus, we enqueue all the stations in that bus route along with the bus count incremented by 1 and mark that bus as visited by adding it into the set of visited buses. If the queue becomes empty and no station is equal to the dest, we return -1 because there is no route available from src to dest.