C++ Coding Test Course, Finding the Fastest Bus Route

Problem Description

In a city, multiple bus routes are operated, and each route circulates through designated stops.
You need to find the fastest route from stop A to stop B.
The bus departs at scheduled times, and you need to consider the time spent at each stop and the travel times.
Given the data below, write an algorithm to find the fastest bus route.

Input Format

  • The first line contains the number of stops N (1 ≤ N ≤ 1000) and the number of bus routes M (1 ≤ M ≤ 10000).
  • From the second line to M lines, information about each bus route is provided in the following format:

    Starting Stop, Ending Stop, Travel Time
  • The last line contains the numbers of stop A and stop B.

Output Format

On the first line, print the shortest time (in minutes) to get from stop A to stop B.
If it is not possible to reach, print -1.

Example Input

    5 7
    1 2 10
    1 3 20
    2 3 5
    2 4 10
    3 4 10
    4 5 15
    1 5

Example Output

    25

Solution Process

To solve this problem, we need to use a shortest path algorithm.
The given graph is a weighted directed graph, so Dijkstra’s algorithm is appropriate.
Dijkstra’s algorithm is a method to find the shortest path from a single starting point to all other vertices,
and can be efficiently applied even when weights are present.

Basic Principle of Dijkstra’s Algorithm

Dijkstra’s algorithm operates on the following basic principles:

  1. Set the starting vertex to initialize the shortest path to 0, and initialize other vertices to infinity.
  2. Select the vertex with the shortest path among the unprocessed vertices.
  3. Update the paths of adjacent vertices of the selected vertex.
  4. Repeat this process until all vertices have been processed.

C++ Code Implementation

Here is a C++ code implementation based on the above algorithm.

    #include 
    #include 
    #include 
    #include 

    using namespace std;

    const int INF = numeric_limits::max();

    void dijkstra(int start, int n, vector>>> &graph, vector &dist) {
        priority_queue, vector>, greater>> pq;
        dist[start] = 0;
        pq.push({0, start});

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            for (auto &neighbor : graph[u]) {
                int v = neighbor.first;
                int weight = neighbor.second;
                
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }
    }

    int main() {
        int N, M;
        cin >> N >> M;
        vector>> graph(N + 1); // N stops

        for (int i = 0; i < M; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u].push_back({v, w});
        }

        int A, B;
        cin >> A >> B;

        vector dist(N + 1, INF);
        dijkstra(A, N, graph, dist);

        if (dist[B] == INF) {
            cout << -1 << endl;
        } else {
            cout << dist[B] << endl;
        }

        return 0;
    }

Code Explanation

The above code implements a method to find the shortest path from the given stop using Dijkstra’s algorithm.
The main steps are as follows:

  1. Store the graph in the adjacency list format based on the given input.
  2. Call the Dijkstra function to find the shortest path from the starting stop to other stops.
  3. As a result, if the shortest path to the destination stop is infinity, it means it cannot be reached, so print -1;
    otherwise, print the time taken for the shortest path.

Conclusion

In this lecture, we addressed the problem of finding the shortest path between the starting point and destination in a graph with multiple bus routes and stops.
We learned the concept of finding the shortest path using Dijkstra’s algorithm and how to implement it.
Based on this, we have laid the foundation to solve other similar problems.