\n This is a problem of finding the K-th shortest path between two nodes A and B in a given graph.
\n The graph is a weighted directed graph. The K-th shortest path refers to the path from A to B
\n whose sum of weights is the K-th smallest among all paths.
\n K is a positive integer and K is always greater than or equal to 1.\n <\/p>\n
\n The first line of the input contains two integers N (1 \u2264 N \u2264 100) and M (1 \u2264 M \u2264 1000).
\n Here, N represents the number of nodes, and M represents the number of edges.
\n Following this, M lines contain three integers U, V, W, which represent an edge with weight W from node U to node V.
\n The last line contains two integers K, A, B. K indicates which K-th shortest path to find,
\n A is the starting node, and B is the destination node.\n <\/p>\n
\n Output the sum of weights of the K-th shortest path. If the K-th shortest path does not exist, output -1.\n <\/p>\n
\n There are various methods to solve this problem, but a variant of the ‘Dijkstra’s Algorithm’ can be used.
\n Dijkstra\u2019s algorithm is typically used to find the shortest path but can utilize a priority queue
\n and path list to find a certain number of shortest paths.
\n The following describes that process.\n <\/p>\n
\n Represent the graph in the form of an adjacency list. Store the connected nodes and their weights for each node.\n <\/p>\n
\n Use a priority queue to manage the weights of paths from the current node to find the shortest path.
\n To find the K-th path, maintain a path list for each node.\n <\/p>\n
\n Start from the starting node and explore paths for each node.
\n The lower the sum of weights of each path, the higher the priority is set,
\n and this process continues until the K-th shortest path is found.\n <\/p>\n
\n Once the sum of weights for the K-th shortest path is successfully calculated, that value is printed.
\n If no path exists, -1 is printed.\n <\/p>\n
Below is the Swift code that uses the method described above.<\/p>\n
\nimport Foundation\n\nstruct Edge {\n let to: Int\n let weight: Int\n}\n\nfunc kthShortestPath(n: Int, edges: [[Edge]], k: Int, start: Int, end: Int) -> Int {\n var paths = [[Int]](repeating: [], count: n + 1)\n var minHeap = [(weight: Int, node: Int)]()\n \n \/\/ Insert (0, start node)\n minHeap.append((0, start))\n \n while !minHeap.isEmpty {\n \/\/ Remove the node with the smallest weight\n minHeap.sort { $0.weight < $1.weight }\n let current = minHeap.removeFirst()\n \n \/\/ Save the path\n paths[current.node].append(current.weight)\n \n \/\/ If the k-th path is found, terminate\n if paths[end].count == k {\n return current.weight\n }\n \n \/\/ Explore adjacent nodes\n for edge in edges[current.node] {\n minHeap.append((current.weight + edge.weight, edge.to))\n }\n }\n \n \/\/ K-th path does not exist\n return -1\n}\n\n\/\/ Input\nlet n = 5 \/\/ Number of nodes\nlet m = 7 \/\/ Number of edges\nlet edges = [\n 1: [Edge(to: 2, weight: 10), Edge(to: 3, weight: 5)],\n 2: [Edge(to: 3, weight: 2), Edge(to: 4, weight: 1)],\n 3: [Edge(to: 2, weight: 3), Edge(to: 4, weight: 9)],\n 4: [Edge(to: 5, weight: 2)],\n 5: []\n]\nlet k = 3 \/\/ K-th path\nlet start = 1 \/\/ Starting node\nlet end = 5 \/\/ Destination node\n\n\/\/ Function call\nlet result = kthShortestPath(n: n, edges: edges, k: k, start: start, end: end)\nprint(result) \/\/ Output result\n <\/code><\/pre>\nConclusion<\/h2>\n
\n The K-th shortest path problem is one of the important techniques in algorithm problem solving.
\n Utilizing Dijkstra's algorithm and priority queues can effectively solve the problem.
\n Additionally, problems like this are often encountered in actual interviews, so sufficient practice is necessary.
\n Through this course, I hope it serves as a foundation for understanding the K-th shortest path problem.\n <\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"