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.<\/p>\n
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.<\/p>\n
Print the length of the K-th shortest path. If the K-th shortest path does not exist, print -1.<\/p>\n
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.<\/p>\n
The data structures used to solve this problem are as follows:<\/p>\n
\n\n#include <iostream>\n#include <vector>\n#include <queue>\n#include <tuple>\n#include <algorithm>\n\nusing namespace std;\n\nconst int INF = 1e9; \/\/ Definition of infinity\n\nstruct Edge {\n int to, weight;\n};\n\nint N, M, K;\nvector<Edge> graph[401];\nvector<int> dist[401]; \/\/ Length of K-th shortest path for each vertex\n\nvoid findKthShortestPath(int start, int end) {\n priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;\n pq.push(make_tuple(0, start, 0)); \/\/ (length, current vertex, number of paths)\n \n while (!pq.empty()) {\n auto [length, current, count] = pq.top();\n pq.pop();\n \n if (count >= K) continue; \/\/ No need to explore more than K paths\n dist[current].push_back(length);\n \n for (auto &edge : graph[current]) {\n int next = edge.to;\n int weight = edge.weight;\n pq.push(make_tuple(length + weight, next, count + 1));\n }\n }\n}\n\nint main() {\n cin >> N >> M >> K; \/\/ Getting vertices, edges, and K\n for (int i = 0; i < M; i++) {\n int u, v, w;\n cin >> u >> v >> w;\n graph[u].push_back({v, w}); \/\/ Adding edge\n }\n\n int A, B;\n cin >> A >> B;\n\n findKthShortestPath(A, B);\n \n if (dist[B].size() < K) {\n cout << -1 << endl; \/\/ Return -1 if K-th shortest path does not exist\n } else {\n cout << dist[B][K-1] << endl; \/\/ Print K-th shortest path\n }\n\n return 0;\n}\n<\/code>\n<\/pre>\nConclusion<\/h2>\n
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.<\/p>\n
I hope you also improve your understanding of graph traversal and elevate your coding skills by practicing this problem. Thank you!<\/p>\n","protected":false},"excerpt":{"rendered":"