Swift Coding Test Course, Finding the Kth Shortest Path

Problem Description

This is a problem of finding the K-th shortest path between two nodes A and B in a given graph.
The graph is a weighted directed graph. The K-th shortest path refers to the path from A to B
whose sum of weights is the K-th smallest among all paths.
K is a positive integer and K is always greater than or equal to 1.

Input Description

The first line of the input contains two integers N (1 ≤ N ≤ 100) and M (1 ≤ M ≤ 1000).
Here, N represents the number of nodes, and M represents the number of edges.
Following this, M lines contain three integers U, V, W, which represent an edge with weight W from node U to node V.
The last line contains two integers K, A, B. K indicates which K-th shortest path to find,
A is the starting node, and B is the destination node.

Output Description

Output the sum of weights of the K-th shortest path. If the K-th shortest path does not exist, output -1.

Problem Solving Process

There are various methods to solve this problem, but a variant of the ‘Dijkstra’s Algorithm’ can be used.
Dijkstra’s algorithm is typically used to find the shortest path but can utilize a priority queue
and path list to find a certain number of shortest paths.
The following describes that process.

1. Graph Representation

Represent the graph in the form of an adjacency list. Store the connected nodes and their weights for each node.

2. Use of Priority Queue

Use a priority queue to manage the weights of paths from the current node to find the shortest path.
To find the K-th path, maintain a path list for each node.

3. Path Calculation

Start from the starting node and explore paths for each node.
The lower the sum of weights of each path, the higher the priority is set,
and this process continues until the K-th shortest path is found.

4. Result Output

Once the sum of weights for the K-th shortest path is successfully calculated, that value is printed.
If no path exists, -1 is printed.

Swift Code Implementation

Below is the Swift code that uses the method described above.

import Foundation

struct Edge {
    let to: Int
    let weight: Int
}

func kthShortestPath(n: Int, edges: [[Edge]], k: Int, start: Int, end: Int) -> Int {
    var paths = [[Int]](repeating: [], count: n + 1)
    var minHeap = [(weight: Int, node: Int)]()
    
    // Insert (0, start node)
    minHeap.append((0, start))
    
    while !minHeap.isEmpty {
        // Remove the node with the smallest weight
        minHeap.sort { $0.weight < $1.weight }
        let current = minHeap.removeFirst()
        
        // Save the path
        paths[current.node].append(current.weight)
        
        // If the k-th path is found, terminate
        if paths[end].count == k {
            return current.weight
        }
        
        // Explore adjacent nodes
        for edge in edges[current.node] {
            minHeap.append((current.weight + edge.weight, edge.to))
        }
    }
    
    // K-th path does not exist
    return -1
}

// Input
let n = 5 // Number of nodes
let m = 7 // Number of edges
let edges = [
    1: [Edge(to: 2, weight: 10), Edge(to: 3, weight: 5)],
    2: [Edge(to: 3, weight: 2), Edge(to: 4, weight: 1)],
    3: [Edge(to: 2, weight: 3), Edge(to: 4, weight: 9)],
    4: [Edge(to: 5, weight: 2)],
    5: []
]
let k = 3 // K-th path
let start = 1 // Starting node
let end = 5 // Destination node

// Function call
let result = kthShortestPath(n: n, edges: edges, k: k, start: start, end: end)
print(result) // Output result
    

Conclusion

The K-th shortest path problem is one of the important techniques in algorithm problem solving.
Utilizing Dijkstra's algorithm and priority queues can effectively solve the problem.
Additionally, problems like this are often encountered in actual interviews, so sufficient practice is necessary.
Through this course, I hope it serves as a foundation for understanding the K-th shortest path problem.