JavaScript Coding Test Course, Finding the K-th Shortest Path

In this course, we will address an algorithm problem that finds the Kth shortest path using JavaScript. This problem requires a solid understanding of graph theory and pathfinding algorithms and focuses on writing efficient code.

Problem Description

Essentially, you need to find the total length of the Kth shortest path among all possible paths from one vertex to another in the given graph.

Problem Input

• N: The number of vertices (1 ≤ N ≤ 100)
• M: The number of edges (1 ≤ M ≤ 1000)
• K: The rank of the desired path (1 ≤ K ≤ 10)
• Afterward, the edge information will be provided over M lines.
  Each edge information is composed of u, v, w, which means that the weight from vertex u to vertex v is w.

Output

Print the total length of the Kth shortest path. If the Kth shortest path does not exist, you should print -1.

Example

    4 5 2
    1 2 4
    1 3 2
    3 2 5
    2 4 1
    3 4 3
    

    5
    

Problem-Solving Approach

To find the Kth shortest path, one of the methods is to modify Dijkstra’s algorithm. The Dijkstra algorithm is primarily used to find the shortest path, but to find the Kth shortest path, it needs to allow for multiple explorations of paths.

Step-by-Step Solution Process

1. Graph Representation

The graph is represented in the form of an adjacency list, with each node storing information about its connected nodes and the weights of those paths. This allows Dijkstra’s algorithm to be applied efficiently.

2. Using a Priority Queue

Using JavaScript’s PriorityQueue to prioritize the exploration of the shortest path. It holds the information of each path, allowing for exploration starting from the minimum cost, just like Dijkstra’s algorithm.

3. Kth Path Exploration

While exploring paths, maintain a count to find the Kth shortest path. Store the lengths of paths in an array, returning the length when the Kth path is reached; otherwise, continue exploring.

4. Result Output

After exploring all paths, output -1 if the Kth path does not exist.

Implementation Code

The code below is a JavaScript version that finds the Kth shortest path based on the explanation above.

class MinHeap {
    constructor() {
        this.heap = [];
    }

    insert(node) {
        this.heap.push(node);
        this.bubbleUp();
    }

    bubbleUp() {
        let index = this.heap.length - 1;
        const element = this.heap[index];

        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            let parent = this.heap[parentIndex];

            if (element[1] >= parent[1]) break;

            this.heap[index] = parent;
            index = parentIndex;
        }
        this.heap[index] = element;
    }

    extractMin() {
        const min = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.sinkDown();
        }
        return min;
    }

    sinkDown() {
        let index = 0;
        const length = this.heap.length;
        const element = this.heap[0];

        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;

            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (leftChild[1] < element[1]) {
                    swap = leftChildIndex;
                }
            }

            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if ((swap === null && rightChild[1] < element[1]) || 
                    (swap !== null && rightChild[1] < leftChild[1])) {
                    swap = rightChildIndex;
                }
            }

            if (swap === null) break;

            this.heap[index] = this.heap[swap];
            index = swap;
        }
        this.heap[index] = element;
    }
}

function kthShortestPath(n, edges, k) {
    const graph = Array.from({ length: n + 1 }, () => []);
    edges.forEach(([u, v, w]) => {
        graph[u].push([v, w]);
    });

    const minHeap = new MinHeap();
    const paths = Array.from({ length: n + 1 }, () => []);

    minHeap.insert([1, 0]);
    paths[1].push(0);

    while (minHeap.heap.length > 0) {
        const [node, distance] = minHeap.extractMin();

        if (paths[node].length === k) continue;

        for (const [neighbor, weight] of graph[node]) {
            const newDistance = distance + weight;

            if (paths[neighbor].length < k) {
                paths[neighbor].push(newDistance);
                paths[neighbor].sort((a, b) => a - b);
                minHeap.insert([neighbor, newDistance]);
            } else if (newDistance < paths[neighbor][paths[neighbor].length - 1]) {
                paths[neighbor][paths[neighbor].length - 1] = newDistance;
                paths[neighbor].sort((a, b) => a - b);
                minHeap.insert([neighbor, newDistance]);
            }
        }
    }

    return paths[n][k - 1] || -1;
}

// Example usage
const n = 4;
const edges = [
    [1, 2, 4],
    [1, 3, 2],
    [3, 2, 5],
    [2, 4, 1],
    [3, 4, 3],
];
const k = 2;

console.log(kthShortestPath(n, edges, k)); // Output: 5

Conclusion

In this course, we discussed algorithms for finding the Kth shortest path. We learned techniques to solve problems based on shortest path algorithms. With this foundation, we can develop the ability to solve more complex graph problems.