Minimum Transfers Between Stops

MediumPython

Problem

Snap operates shuttle routes between Snap offices and event venues. Given the stops served by each shuttle route, a starting stop, and a destination stop, return the minimum number of transfers needed to reach the destination. A passenger may board any route serving the current stop and may ride it to any of its stops. Return -1 if the destination is unreachable.

A direct ride requires 0 transfers. If reaching the destination requires boarding two different routes, the answer is 1. If start_stop == end_stop, return 0.

Formal Specification

Implement min_transfers(routes, start_stop, end_stop).

routes is a list of routes, where routes[i] is a list of integer stop IDs served by route i.
start_stop and end_stop are integer stop IDs.
Return an integer representing the minimum number of route changes, or -1 when no route sequence can connect the stops.
A route may contain many stops, and stops can be shared by multiple routes.

Constraints

1 <= len(routes) <= 10^5
The total number of stops across all routes is at most 2 * 10^5
0 <= start_stop, end_stop <= 10^9
Each route contains no duplicate stop IDs
A stop can be served by multiple routes

Function Signature

def min_transfers(routes, start_stop, end_stop):

A direct ride requires 0 transfers. If reaching the destination requires boarding two different routes, the answer is 1. If start_stop == end_stop, return 0.

Formal Specification

Implement min_transfers(routes, start_stop, end_stop).

routes is a list of routes, where routes[i] is a list of integer stop IDs served by route i.
start_stop and end_stop are integer stop IDs.
Return an integer representing the minimum number of route changes, or -1 when no route sequence can connect the stops.
A route may contain many stops, and stops can be shared by multiple routes.