0
$\begingroup$

https://leetcode.com/problems/bus-routes/

You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.

For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever. You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.

The solutions for this problem involve doing a BFS from each of the vertices(bus stops), but how does that guarantee a the minimum path ?

$\endgroup$

1 Answer 1

1
$\begingroup$

BFS (or Breadth-First Search) from its name implies that it will search for the destination along the breadth. That means it looks at all the current possible routes ie nodes connected to the current one and divides itself into all of those. Basically, at every junction, it divides itself and continues down that path until it encounters the destination node.

So effectively, it can be said that it checks for all the paths of length len from the source node starting len from 0 and incrementing it by 1 until it reaches the destination.

Let's say it got to the destination with length 7, now this means that it tried all the paths of length 0, 1, 2 ... 6 but was not able to get to the destination.

So, this means that whenever BFS finds a path, it already tried all paths of length (or cost) lower than the current one but was able to find a complete path that reaches the destination. Which means it always finds the shortest (or cheapest) path.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.