Python Coding Test Course, Finding the Fastest Bus Route

This course covers the problem of Finding the Fastest Bus Route, 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.

Problem Description

There is a city with N vertices from 1 to N. 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 to vertex N and the time it takes.

Input Format

• The first line contains the number of vertices N (1 ≤ N ≤ 1000) and the number of bus routes M (1 ≤ M ≤ 10000).
• The next M lines provide the information for each bus route in the format u v w, where w is the travel time from u to v (1 ≤ w ≤ 10000).

Output Format

• Print the fastest travel time from vertex 1 to vertex N. If there is no route, print -1.

Problem Solving Process

1. Understanding the Problem

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 1 to vertex N.

2. Selecting the Algorithm

There are various algorithms to find the shortest path, but here we will use the Dijkstra’s Algorithm. 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.

3. Implementing the Algorithm

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.

# Import required libraries
import sys
import heapq

def dijkstra(N, edges):
    # Initialize distance array
    distance = [float('inf')] * (N + 1)
    distance[1] = 0  # Distance to starting vertex 1 is 0
    priority_queue = [(0, 1)]  # (distance, vertex)

    # Initialize graph
    graph = [[] for _ in range(N + 1)]
    for u, v, w in edges:
        graph[u].append((v, w))

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        if current_distance > distance[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex]:
            distance_via_neighbor = current_distance + weight
            
            if distance_via_neighbor < distance[neighbor]:
                distance[neighbor] = distance_via_neighbor
                heapq.heappush(priority_queue, (distance_via_neighbor, neighbor))

    return distance[N] if distance[N] != float('inf') else -1

# Input
N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
result = dijkstra(N, edges)

print(result)

4. Example and Test Cases

To verify the appropriateness of this algorithm, let's consider several input examples.

Example 1

Input:
4 5
1 2 1
1 3 4
2 3 2
3 4 1
2 4 5

Output:
3

Explanation: The shortest path from vertex 1 to vertex 4 is 1 → 2 → 3 → 4, with a total travel time of 3.

Example 2

Input:
3 3
1 2 1
1 3 4
3 2 2

Output:
-1

Explanation: There is no route from vertex 1 to vertex 2, so we output -1.

Conclusion

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.