C++ Coding Test Course, Finding the Kth Shortest Path

Hello! In this course, we will talk about one of the algorithm problems, “Finding the K-th Shortest Path”. This problem frequently appears in real coding tests and requires a deep understanding of graphs and shortest path algorithms. Through this problem, we will learn how to utilize Dijkstra’s algorithm and priority queues.

Problem Description

The problem is to find the length of the K-th shortest path between two vertices A and B in the given graph. The shortest path refers to the path with the shortest length among multiple paths, and the K-th shortest path refers to the shortest path that is longer than the shortest path. The same path can exist multiple times.

Input

• Number of vertices N (1 ≤ N ≤ 400)
• Number of edges M (1 ≤ M ≤ 100,000)
• K (1 ≤ K ≤ 3000)
• Information of each edge (starting vertex, ending vertex, weight)
• Vertices A and B

Output

Print the length of the K-th shortest path. If the K-th shortest path does not exist, print -1.

Problem Approach

To solve this problem, we need to think about how to find the K-th shortest path. The standard Dijkstra’s algorithm is effective for finding the shortest path, but additional measures are needed to find the K-th path.

The data structures used to solve this problem are as follows:

• Priority Queue: Ensures that the smallest value is handled first.
• Vector: Used to represent the graph structure.

Algorithm Steps

1. Input the graph and represent it as an adjacent list.
2. Store the path list for each vertex in a priority queue.
3. Use Dijkstra’s algorithm from the starting vertex to find the K-th shortest path.
4. Find and print the K-th smallest value from the path list.

C++ Code Implementation

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

const int INF = 1e9;  // Definition of infinity

struct Edge {
    int to, weight;
};

int N, M, K;
vector<Edge> graph[401];
vector<int> dist[401];  // Length of K-th shortest path for each vertex

void findKthShortestPath(int start, int end) {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.push(make_tuple(0, start, 0));  // (length, current vertex, number of paths)
    
    while (!pq.empty()) {
        auto [length, current, count] = pq.top();
        pq.pop();
        
        if (count >= K) continue; // No need to explore more than K paths
        dist[current].push_back(length);
        
        for (auto &edge : graph[current]) {
            int next = edge.to;
            int weight = edge.weight;
            pq.push(make_tuple(length + weight, next, count + 1));
        }
    }
}

int main() {
    cin >> N >> M >> K; // Getting vertices, edges, and K
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w}); // Adding edge
    }

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

    findKthShortestPath(A, B);
    
    if (dist[B].size() < K) {
        cout << -1 << endl; // Return -1 if K-th shortest path does not exist
    } else {
        cout << dist[B][K-1] << endl; // Print K-th shortest path
    }

    return 0;
}

Conclusion

In this course, we have explored various methods of graph traversal and efficient pathfinding using priority queues through the problem of finding the K-th shortest path. In the process of solving this problem, we learned how to find the K-th path by modifying Dijkstra’s algorithm. Understanding such problems will provide opportunities to achieve high scores in actual coding tests.

I hope you also improve your understanding of graph traversal and elevate your coding skills by practicing this problem. Thank you!