Java Coding Test Course, Finding the Fastest Bus Route

In this article, we will address the problem of “Finding the Fastest Bus Route,” which may appear in coding tests using Java. The shortest path problem using buses is an excellent example for grasping the basic concepts of greedy algorithms and graph theory. Through this, we will enhance our algorithm problem-solving skills and improve our Java coding abilities.

Problem Description

There are several bus routes between the given city A and city B, each with information about specific departure and arrival times. The bus routes have different travel times and fares, and we need to choose the fastest route among many.

Input

The input is provided in the following format:

  • The first line receives information about city A and city B.
  • The second line gives the number of bus routes N.
  • The following N lines each provide the starting city, ending city, travel time, and fare for each bus route.

Output

Print the travel time for the fastest bus. If it is not possible to reach, print “Cannot arrive.”

Example

    Input:
    A B
    3
    A B 5 3000
    A B 3 2500
    B A 2 1500

    Output:
    3

Problem Solving Process

1. Understanding the Problem

The first thing to do is to thoroughly understand the problem. It is important to note that there are multiple routes, and each route has different starting points, endpoints, travel times, and fares. This problem can be summarized as finding the shortest path. We need to find the shortest path from the starting city A to the destination city B.

2. Algorithm Selection

The most suitable algorithm to solve this problem is Dijkstra’s shortest path algorithm. This is an efficient algorithm that finds the shortest path between two vertices in a weighted graph where the weights represent travel times. Additionally, it can be implemented using Java.

3. Implementing Dijkstra’s Algorithm

Next is the process of implementing Dijkstra’s algorithm in Java. First, we will define the necessary classes and set up the data structures to store information about each city and route.

    import java.util.*;

    public class BusRoute {
        static class Route {
            String destination;
            int time;
            int price;

            public Route(String destination, int time, int price) {
                this.destination = destination;
                this.time = time;
                this.price = price;
            }
        }

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String start = sc.nextLine(); // Starting city
            String end = sc.nextLine();   // Destination city
            int N = sc.nextInt();         // Number of routes
            Map> graph = new HashMap<>();

            for (int i = 0; i < N; i++) {
                String from = sc.next();
                String to = sc.next();
                int time = sc.nextInt();
                int price = sc.nextInt();
                graph.computeIfAbsent(from, k -> new ArrayList<>()).add(new Route(to, time, price));
            }

            // Call Dijkstra's algorithm
            int shortestTime = dijkstra(start, end, graph);

            // Output result
            if (shortestTime == Integer.MAX_VALUE) {
                System.out.println("Cannot arrive.");
            } else {
                System.out.println(shortestTime);
            }
        }
    }

4. Core Logic of Dijkstra’s Algorithm

To implement Dijkstra’s algorithm, we first use a priority queue to store the shortest time information and city information. While exploring the connected cities from each current city, we update based on the array that records the current travel time. Below is the implementation of the Dijkstra function.

    public static int dijkstra(String start, String end, Map> graph) {
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(r -> r.time));
        Map minTime = new HashMap<>();

        pq.add(new Route(start, 0, 0)); // Add starting city
        minTime.put(start, 0);

        while (!pq.isEmpty()) {
            Route current = pq.poll();

            // Reached the destination
            if (current.destination.equals(end)) {
                return current.time;
            }

            // Explore routes connected to the current city
            for (Route route : graph.getOrDefault(current.destination, Collections.emptyList())) {
                int newTime = current.time + route.time;

                if (newTime < minTime.getOrDefault(route.destination, Integer.MAX_VALUE)) {
                    minTime.put(route.destination, newTime);
                    pq.add(new Route(route.destination, newTime, route.price));
                }
            }
        }

        return Integer.MAX_VALUE; // Cannot arrive
    }

5. Code Explanation

In the code above, Dijkstra's algorithm uses a priority queue to prioritize reviewing the fastest routes. It selects the city with the lowest travel time and proceeds to travel to other cities connected to that city. If the new travel time is shorter than the recorded time, it updates the information and continues exploring ahead.

Conclusion

In this post, we examined the process of implementing Dijkstra's algorithm in Java through the problem of "Finding the Fastest Bus Route." When solving algorithm problems, it is essential to understand the essence of the problem and choose an effective algorithm. This example is very useful for preparing for coding tests and is a skill that can be applied to other similar problems.

I hope you can cultivate algorithmic thinking by breaking down complex problems into manageable steps. Next time, I will explore more diverse algorithms and problem-solving methods!

© 2023 Blog Author