Problem Introduction
You need to write a program that finds the fastest bus route from point A to point B. There are multiple bus routes, and each route passes through specified stops, with different travel times between stops. The ultimate goal is to find the fastest path from a specific point A to point B and return the travel time for that path.
Problem Description
The given routes are expressed as follows. Each route has travel times between stops, and the stops are represented in the following format:
[
{busRoute: "1", stops: [{stop: "A", time: 0}, {stop: "B", time: 5}, {stop: "C", time: 10}]},
{busRoute: "2", stops: [{stop: "A", time: 0}, {stop: "D", time: 3}, {stop: "B", time: 8}]},
{busRoute: "3", stops: [{stop: "B", time: 0}, {stop: "C", time: 4}, {stop: "E", time: 6}]},
{busRoute: "4", stops: [{stop: "D", time: 0}, {stop: "E", time: 2}, {stop: "B", time: 7}]},
]
Input
The first parameter is an array of bus routes, and the second parameter is point A and point B.
Output
Print the travel time of the fastest route. If there is no route, print -1.
Example
Input:
const routes = [
{busRoute: "1", stops: [{stop: "A", time: 0}, {stop: "B", time: 5}, {stop: "C", time: 10}]},
{busRoute: "2", stops: [{stop: "A", time: 0}, {stop: "D", time: 3}, {stop: "B", time: 8}]},
{busRoute: "3", stops: [{stop: "B", time: 0}, {stop: "C", time: 4}, {stop: "E", time: 6}]},
{busRoute: "4", stops: [{stop: "D", time: 0}, {stop: "E", time: 2}, {stop: "B", time: 7}]},
];
const start = "A";
const end = "B";
Output:
5
Solution Method
To solve this problem, we can use a graph traversal algorithm. The stops represent nodes, and the travel times between stops represent the weights of the edges between those nodes. Suitable algorithms include BFS (Breadth-First Search) or Dijkstra’s algorithm. In this problem, Dijkstra’s algorithm is more effective because the weights of all edges may differ, necessitating an optimized method to find the shortest path.
Dijkstra’s Algorithm Overview
Dijkstra’s algorithm is used to find the shortest path in a weighted graph, continuously updating the cost of moving from the current node to adjacent nodes while exploring the path to the target node. For this, we use a priority queue to record each stop and its cost.
Code Implementation
function getFastestBusRoute(routes, start, end) {
// Priority queue for processing the stops
const pq = new MinPriorityQueue();
const distances = {};
const parents = {};
// Initialize distances and priority queue
for (const route of routes) {
for (const stop of route.stops) {
distances[stop.stop] = Infinity;
parents[stop.stop] = null;
}
}
// Starting point
distances[start] = 0;
pq.enqueue(start, 0);
while (!pq.isEmpty()) {
const currentStop = pq.dequeue().element;
// If we reach the target stop, return the distance
if (currentStop === end) {
return distances[currentStop];
}
for (const route of routes) {
for (let i = 0; i < route.stops.length - 1; i++) {
const stop1 = route.stops[i].stop;
const stop2 = route.stops[i + 1].stop;
const time = route.stops[i + 1].time - route.stops[i].time;
if (stop1 === currentStop) {
const newTime = distances[stop1] + time;
if (newTime < distances[stop2]) {
distances[stop2] = newTime;
parents[stop2] = stop1;
pq.enqueue(stop2, newTime);
}
}
}
}
}
return -1; // If there's no path to the end
}
// Example usage
const routes = [
{busRoute: "1", stops: [{stop: "A", time: 0}, {stop: "B", time: 5}, {stop: "C", time: 10}]},
{busRoute: "2", stops: [{stop: "A", time: 0}, {stop: "D", time: 3}, {stop: "B", time: 8}]},
{busRoute: "3", stops: [{stop: "B", time: 0}, {stop: "C", time: 4}, {stop: "E", time: 6}]},
{busRoute: "4", stops: [{stop: "D", time: 0}, {stop: "E", time: 2}, {stop: "B", time: 7}]},
];
const start = "A";
const end = "B";
console.log(getFastestBusRoute(routes, start, end)); // Output: 5
Conclusion
In this lecture, we learned how to solve the algorithm problem of finding the fastest path based on the given bus route information. Dijkstra's algorithm is a very useful method for finding the shortest path in weighted graphs. I hope you found it helpful to understand how to explore at each step and implement it in code.
Additional Practice Problems
If you've learned Dijkstra's algorithm through this problem, try tackling the following variations:
- A problem where you must find a route using only specific lines
- A problem that finds routes based on travel distance instead of travel time between stops
- A problem that finds the maximum path instead of the minimum path