Java Coding Test Course, K-th Shortest Path Finding

Finding the Kth shortest path is one of the commonly discussed problems in graph theory. It involves finding the Kth shortest path between two given vertices,
where understanding the characteristics of the graph and applying the appropriate algorithm is essential. This article will detail the definition of this problem,
methods to solve it, and its implementation in Java.

Problem Definition

Let’s consider the problem of finding the Kth shortest path between two vertices A and B in a given directed graph.
Here, the “shortest path” refers to the path with the minimum sum of weights among all paths. The Kth shortest path is found by first identifying the shortest path,
then the second shortest, and so on, until the Kth path is found.

Input

Number of vertices N (1 ≤ N ≤ 100)
Number of edges M (1 ≤ M ≤ 500)
Information about each edge (starting vertex, ending vertex, weight)
Starting vertex A, ending vertex B, K

Output

Output the length of the Kth shortest path from vertex A to B.
If the Kth shortest path does not exist, output -1.

Algorithm Overview

The algorithm used to solve the Kth shortest path problem can be a variation of Dijkstra’s algorithm.
The standard Dijkstra algorithm finds the shortest paths from the starting vertex to all other vertices.
To find the Kth shortest path, some modifications to this algorithm are necessary.

Approach to Solve the Problem

1. Use a Priority Queue to store the Kth shortest path for each vertex.
2. Maintain the shortest paths for each vertex in list form and explore paths using the priority queue.
3. Update the Kth shortest path while exploring the paths.

Step-by-Step Explanation

Initialize Priority Queue: Create a structure that can store up to K shortest paths for each vertex.
Perform Dijkstra’s Algorithm: Start from the starting vertex, calculate the sum of weights to adjacent vertices, and add them to the priority queue.
Check Kth Path: When reaching vertex B, check the length of the Kth path.

Java Code Implementation

Below is the Java code for finding the Kth shortest path:


import java.util.*;

class Edge {
    int to, weight;

    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

class KthShortestPath {
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // Number of vertices
        int M = sc.nextInt(); // Number of edges
        int K = sc.nextInt(); // K

        List[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            graph[u].add(new Edge(v, w));
        }

        int start = sc.nextInt();
        int end = sc.nextInt();

        System.out.println(findKthShortestPath(graph, N, start, end, K));
    }

    static int findKthShortestPath(List[] graph, int N, int start, int end, int K) {
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        List[] minHeap = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            minHeap[i] = new ArrayList<>();
        }

        pq.add(new int[]{0, start}); // {length, vertex}
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currLength = current[0];
            int currNode = current[1];

            minHeap[currNode].add(currLength);
            if (minHeap[currNode].size() > K) {
                continue;
            }

            for (Edge edge : graph[currNode]) {
                int nextNode = edge.to;
                int nextLength = currLength + edge.weight;

                pq.add(new int[]{nextLength, nextNode});
            }
        }

        if (minHeap[end].size() < K) {
            return -1;
        }
        return minHeap[end].get(K - 1);
    }
}

Example Input and Output

Input Example

Output Example

Conclusion

Finding the Kth shortest path is greatly helpful in understanding graphs and solving problems by selecting the appropriate algorithm.
Learning to find the Kth shortest path by modifying Dijkstra's algorithm can be useful in various coding tests.

Through this article, you learned to understand the Kth shortest path problem and how to implement it in Java.
Keep solving various algorithm problems to improve your skills!