Samanatha123
New member
- Joined
- May 3, 2021
- Messages
- 7
i am struggling to picture this in my head. I know that you can do the whole route on line A, the whole route on line B or start on line A and transfer to B. But how would I do BFS on this?There would be sites on each line and I would do bfs on them.
A city map consists of n bus stations. There are only two main bus lines: Line A and line B. The bus lines provide travel between bus stations. Two bus stations may be connected by line A, line B, or both. One bus station is at your work, station W, and one bus station is at your home, station H. You are interested in the minimum number of stops (at a station) required to go from your work to your home. However, you may only change bus lines at most once. Changing bus lines is only allowed from line A to line B. This means you may either do the whole route on line A, the whole route on line B, or start on line A and transfer to line B. Describe an algorithm that determines the minimum number of stops to get from your work to your home. Justify the runtime of O(V + E).
Hint: use BFS and consider all possible stations as places where you may transfer lines.)
A city map consists of n bus stations. There are only two main bus lines: Line A and line B. The bus lines provide travel between bus stations. Two bus stations may be connected by line A, line B, or both. One bus station is at your work, station W, and one bus station is at your home, station H. You are interested in the minimum number of stops (at a station) required to go from your work to your home. However, you may only change bus lines at most once. Changing bus lines is only allowed from line A to line B. This means you may either do the whole route on line A, the whole route on line B, or start on line A and transfer to line B. Describe an algorithm that determines the minimum number of stops to get from your work to your home. Justify the runtime of O(V + E).
Hint: use BFS and consider all possible stations as places where you may transfer lines.)