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.<\/p>\n
\n The given routes are expressed as follows. Each route has travel times between stops, and the stops are represented in the following format:\n <\/p>\n
\n [\n {busRoute: \"1\", stops: [{stop: \"A\", time: 0}, {stop: \"B\", time: 5}, {stop: \"C\", time: 10}]},\n {busRoute: \"2\", stops: [{stop: \"A\", time: 0}, {stop: \"D\", time: 3}, {stop: \"B\", time: 8}]},\n {busRoute: \"3\", stops: [{stop: \"B\", time: 0}, {stop: \"C\", time: 4}, {stop: \"E\", time: 6}]},\n {busRoute: \"4\", stops: [{stop: \"D\", time: 0}, {stop: \"E\", time: 2}, {stop: \"B\", time: 7}]},\n ]\n <\/pre>\nInput<\/h2>\n
The first parameter is an array of bus routes, and the second parameter is point A and point B.<\/p>\n
Output<\/h2>\n
Print the travel time of the fastest route. If there is no route, print -1.<\/p>\n
Example<\/h2>\n\n Input: \n const routes = [\n {busRoute: \"1\", stops: [{stop: \"A\", time: 0}, {stop: \"B\", time: 5}, {stop: \"C\", time: 10}]},\n {busRoute: \"2\", stops: [{stop: \"A\", time: 0}, {stop: \"D\", time: 3}, {stop: \"B\", time: 8}]},\n {busRoute: \"3\", stops: [{stop: \"B\", time: 0}, {stop: \"C\", time: 4}, {stop: \"E\", time: 6}]},\n {busRoute: \"4\", stops: [{stop: \"D\", time: 0}, {stop: \"E\", time: 2}, {stop: \"B\", time: 7}]},\n ];\n const start = \"A\";\n const end = \"B\";\n\n Output: \n 5\n <\/pre>\nSolution Method<\/h2>\n
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.<\/p>\n
Dijkstra’s Algorithm Overview<\/h3>\n
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.<\/p>\n
Code Implementation<\/h2>\n\n function getFastestBusRoute(routes, start, end) {\n \/\/ Priority queue for processing the stops\n const pq = new MinPriorityQueue();\n const distances = {};\n const parents = {};\n\n \/\/ Initialize distances and priority queue\n for (const route of routes) {\n for (const stop of route.stops) {\n distances[stop.stop] = Infinity;\n parents[stop.stop] = null;\n }\n }\n\n \/\/ Starting point\n distances[start] = 0;\n pq.enqueue(start, 0);\n\n while (!pq.isEmpty()) {\n const currentStop = pq.dequeue().element;\n\n \/\/ If we reach the target stop, return the distance\n if (currentStop === end) {\n return distances[currentStop];\n }\n\n for (const route of routes) {\n for (let i = 0; i < route.stops.length - 1; i++) {\n const stop1 = route.stops[i].stop;\n const stop2 = route.stops[i + 1].stop;\n const time = route.stops[i + 1].time - route.stops[i].time;\n\n if (stop1 === currentStop) {\n const newTime = distances[stop1] + time;\n if (newTime < distances[stop2]) {\n distances[stop2] = newTime;\n parents[stop2] = stop1;\n pq.enqueue(stop2, newTime);\n }\n }\n }\n }\n }\n return -1; \/\/ If there's no path to the end\n }\n\n \/\/ Example usage\n const routes = [\n {busRoute: \"1\", stops: [{stop: \"A\", time: 0}, {stop: \"B\", time: 5}, {stop: \"C\", time: 10}]},\n {busRoute: \"2\", stops: [{stop: \"A\", time: 0}, {stop: \"D\", time: 3}, {stop: \"B\", time: 8}]},\n {busRoute: \"3\", stops: [{stop: \"B\", time: 0}, {stop: \"C\", time: 4}, {stop: \"E\", time: 6}]},\n {busRoute: \"4\", stops: [{stop: \"D\", time: 0}, {stop: \"E\", time: 2}, {stop: \"B\", time: 7}]},\n ];\n const start = \"A\";\n const end = \"B\";\n console.log(getFastestBusRoute(routes, start, end)); \/\/ Output: 5\n <\/pre>\nConclusion<\/h2>\n
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.<\/p>\n
Additional Practice Problems<\/h2>\n
If you've learned Dijkstra's algorithm through this problem, try tackling the following variations:<\/p>\n
\n- A problem where you must find a route using only specific lines<\/li>\n
- A problem that finds routes based on travel distance instead of travel time between stops<\/li>\n
- A problem that finds the maximum path instead of the minimum path<\/li>\n<\/ul>\n
References<\/h2>\n