This course covers the problem of Finding the Fastest Bus Route<\/strong>, which is frequently presented in actual job exam algorithm problems. This problem can be solved using graph theory and shortest path algorithms. Throughout the course, we will enhance our algorithm problem-solving skills and learn various techniques necessary for writing Python code.<\/p>\n There is a city with This problem is a representative type of graph problem in finding the shortest path. When bus routes are represented as a graph, each vertex corresponds to a bus stop, edges represent bus routes, and the weights of the edges can be thought of as the travel times. What we want to solve is the fastest way to move from vertex There are various algorithms to find the shortest path, but here we will use the Dijkstra’s Algorithm<\/strong>. Dijkstra’s algorithm is efficient for finding the shortest paths in graphs with non-negative weights. Since the travel times for the given bus routes are all positive, this algorithm is appropriate.<\/p>\n The basic idea of Dijkstra’s algorithm is to maintain an array that records the shortest path distances to each vertex while selecting the vertex with the currently shortest distance. The detailed implementation process is as follows.<\/p>\n To verify the appropriateness of this algorithm, let's consider several input examples.<\/p>\n Explanation: The shortest path from vertex 1 to vertex 4 is 1 \u2192 2 \u2192 3 \u2192 4, with a total travel time of 3.<\/p>\n Explanation: There is no route from vertex 1 to vertex 2, so we output -1.<\/p>\n In this course, we learned how to solve the problem of finding the fastest bus route using Dijkstra's algorithm for the shortest path. I hope this has been helpful in understanding and implementing the algorithm. As you may encounter similar problems in future coding tests, I encourage you to continue practicing.<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Description<\/h2>\n
N<\/code> vertices from 1<\/code> to N<\/code>. There are several bus routes between each pair of vertices, and each bus route has a departure and arrival vertex along with a travel time. Based on the given information, find the fastest route from vertex 1<\/code> to vertex N<\/code> and the time it takes.<\/p>\nInput Format<\/h3>\n
\n
N<\/code> (1 \u2264 N \u2264 1000) and the number of bus routes M<\/code> (1 \u2264 M \u2264 10000).<\/li>\nM<\/code> lines provide the information for each bus route in the format u v w<\/code>, where w<\/code> is the travel time from u<\/code> to v<\/code> (1 \u2264 w \u2264 10000).<\/li>\n<\/ul>\nOutput Format<\/h3>\n
\n
1<\/code> to vertex N<\/code>. If there is no route, print -1<\/code>.<\/li>\n<\/ul>\nProblem Solving Process<\/h2>\n
1. Understanding the Problem<\/h3>\n
1<\/code> to vertex N<\/code>.<\/p>\n2. Selecting the Algorithm<\/h3>\n
3. Implementing the Algorithm<\/h3>\n
\n# Import required libraries\nimport sys\nimport heapq\n\ndef dijkstra(N, edges):\n # Initialize distance array\n distance = [float('inf')] * (N + 1)\n distance[1] = 0 # Distance to starting vertex 1 is 0\n priority_queue = [(0, 1)] # (distance, vertex)\n\n # Initialize graph\n graph = [[] for _ in range(N + 1)]\n for u, v, w in edges:\n graph[u].append((v, w))\n\n while priority_queue:\n current_distance, current_vertex = heapq.heappop(priority_queue)\n \n if current_distance > distance[current_vertex]:\n continue\n\n for neighbor, weight in graph[current_vertex]:\n distance_via_neighbor = current_distance + weight\n \n if distance_via_neighbor < distance[neighbor]:\n distance[neighbor] = distance_via_neighbor\n heapq.heappush(priority_queue, (distance_via_neighbor, neighbor))\n\n return distance[N] if distance[N] != float('inf') else -1\n\n# Input\nN, M = map(int, input().split())\nedges = [tuple(map(int, input().split())) for _ in range(M)]\nresult = dijkstra(N, edges)\n\nprint(result)\n<\/pre>\n4. Example and Test Cases<\/h3>\n
Example 1<\/h4>\n
\nInput:\n4 5\n1 2 1\n1 3 4\n2 3 2\n3 4 1\n2 4 5\n\nOutput:\n3\n<\/pre>\n
Example 2<\/h4>\n
\nInput:\n3 3\n1 2 1\n1 3 4\n3 2 2\n\nOutput:\n-1\n<\/pre>\n
Conclusion<\/h2>\n