Learning Journal

3/8/2024

Network Delay Time - Dijkstra's Algorithm

Tags: algorithms leetcode heap_sort graph

function networkDelayTime(times: number[][], n: number, k: number): number {
    const adjList:Record<string, [number,number, number][]> = {};

    for(let i = 0; i < times.length; i++) {
        if(!adjList[times[i][0]]){
            adjList[times[i][0]] = [[times[i][0], times[i][1], times[i][2]]];
        }
        else {
            adjList[times[i][0]].push([times[i][0], times[i][1], times[i][2]]);
        }
    }
    

    const minTimes = Array(n+1).fill(Infinity);
    minTimes[k] = 0;

    const minHeap = new MinHeap();
    const edges = adjList[String(k)];

    if(!edges) return -1;

    for(let i = 0; i < edges.length; i++)
        minHeap.add(edges[i]); 


    while(!minHeap.isEmpty()){
        const [source, target, time] = minHeap.pop();
                
        if(minTimes[target] > minTimes[source] + time) {

            minTimes[target] = minTimes[source] + time;

            const edges = adjList[target];
            
            if(!edges) continue;


            for(let i = 0; i< edges.length; i++) {
                minHeap.add(edges[i]);
            }
        }

    }

    let max = 0;


    for(let i = 1; i < minTimes.length; i++) {
        if(minTimes[i] === Infinity)
            return -1;
        else if(max < minTimes[i])
            max = minTimes[i];
    }

    return max;
};

class MinHeap {
    private arr:[number,number,number][] = [];
    
    isEmpty():boolean {
        return this.arr.length === 0;
    }


    add(e:[number,number,number]){
        this.arr.push(e);

        let curI = this.arr.length - 1, parentI = this.getParentI(curI);

        while(curI > 0 && this.arr[curI][2] < this.arr[parentI][2]){
            this.swap(curI, parentI);
            curI = parentI;
            parentI =  this.getParentI(curI);
        }
    }

    pop():[number,number,number]{
        const retE = this.arr[0];
        const last = this.arr.pop();

        if(this.arr.length === 0) return retE;

        this.arr[0] = last;

        let curI = 0, leftChildI = this.getLeftChildI(curI), rightChildI = this.getRightChildI(curI);

        while((leftChildI < this.arr.length && this.arr[leftChildI][2] < this.arr[curI][2])
                || (rightChildI < this.arr.length && this.arr[rightChildI][2] < this.arr[curI][2])) {
                    const smallerChildI = (rightChildI >= this.arr.length || this.arr[rightChildI][2] > this.arr[leftChildI][2])
                                            ? leftChildI : rightChildI;

                    this.swap(smallerChildI, curI);
                    curI = smallerChildI;
                    leftChildI  = this.getLeftChildI(curI);
                    rightChildI = this.getRightChildI(curI);
                }

        return retE;
    }

    private swap(i:number, j:number) {
        const temp = this.arr[i];
        this.arr[i] = this.arr[j];
        this.arr[j] = temp;
    }

    private getParentI(i:number) {
        return Math.floor((i - 1)/2);
    }

    private getLeftChildI(i:number) {
        return 2*i + 1;
    }

    private getRightChildI(i:number) {
        return 2*i + 2;
    }
}


function networkDelayTime(times: number[][], n: number, k: number): number {
    const adjList:Record<string, [number,number, number][]> = {};

    for(let i = 0; i < times.length; i++) {
        if(!adjList[times[i][0]]){
            adjList[times[i][0]] = [[times[i][0], times[i][1], times[i][2]]];
        }
        else {
            adjList[times[i][0]].push([times[i][0], times[i][1], times[i][2]]);
        }
    }
    

    const minTimes = Array(n+1).fill(Infinity);
    minTimes[k] = 0;

    const minHeap = new MinHeap();
    const edges = adjList[String(k)];

    if(!edges) return -1;

    for(let i = 0; i < edges.length; i++)
        minHeap.add(edges[i]); 


    while(!minHeap.isEmpty()){
        const [source, target, time] = minHeap.pop();
                
        if(minTimes[target] > minTimes[source] + time) {

            minTimes[target] = minTimes[source] + time;

            const edges = adjList[target];
            
            if(!edges) continue;


            for(let i = 0; i< edges.length; i++) {
                minHeap.add(edges[i]);
            }
        }

    }

    let max = 0;


    for(let i = 1; i < minTimes.length; i++) {
        if(minTimes[i] === Infinity)
            return -1;
        else if(max < minTimes[i])
            max = minTimes[i];
    }

    return max;
};

class MinHeap {
    private arr:[number,number,number][] = [];
    
    isEmpty():boolean {
        return this.arr.length === 0;
    }


    add(e:[number,number,number]){
        this.arr.push(e);

        let curI = this.arr.length - 1, parentI = this.getParentI(curI);

        while(curI > 0 && this.arr[curI][2] < this.arr[parentI][2]){
            this.swap(curI, parentI);
            curI = parentI;
            parentI =  this.getParentI(curI);
        }
    }

    pop():[number,number,number]{
        const retE = this.arr[0];
        const last = this.arr.pop();

        if(this.arr.length === 0) return retE;

        this.arr[0] = last;

        let curI = 0, leftChildI = this.getLeftChildI(curI), rightChildI = this.getRightChildI(curI);

        while((leftChildI < this.arr.length && this.arr[leftChildI][2] < this.arr[curI][2])
                || (rightChildI < this.arr.length && this.arr[rightChildI][2] < this.arr[curI][2])) {
                    const smallerChildI = (rightChildI >= this.arr.length || this.arr[rightChildI][2] > this.arr[leftChildI][2])
                                            ? leftChildI : rightChildI;

                    this.swap(smallerChildI, curI);
                    curI = smallerChildI;
                    leftChildI  = this.getLeftChildI(curI);
                    rightChildI = this.getRightChildI(curI);
                }

        return retE;
    }

    private swap(i:number, j:number) {
        const temp = this.arr[i];
        this.arr[i] = this.arr[j];
        this.arr[j] = temp;
    }

    private getParentI(i:number) {
        return Math.floor((i - 1)/2);
    }

    private getLeftChildI(i:number) {
        return 2*i + 1;
    }

    private getRightChildI(i:number) {
        return 2*i + 2;
    }
}

THE PROBLEM

This time, I try to solve this problem using Dijkstra's Algorithm.

In general, Dijkstra's algorithm is used to find the shortest path between a given node and all other nodes in a graph. So, the plan is to use Dijkstra's to find such path, then find the time to reach the furthest node in that path to return. If Dijkstra's can not reach all nodes in the graph, we return -1. Dijkstra's algorithm works as follows. Our path starts from the source node. Consider all edges coming from the source node. Add the shortest edge and the node that edge leads to (let call it target node) to our path. Add all the edges coming from the target node into consideration set. Repeated until there is no edge to consider. During the process, if after we add a certain edge and discover that the path coming through this edge to the target node is shorter than the current path coming to the target node (without going through this edge), we replace the current path with the new path. So, this is basically what my code does:

Create an array to store the shortest time to reach each node. Let call it minTimes. minTimes has n + 1 element because the nodes is numbered starting at 1. Set all elements of minTimes to Infinity, except the source node element, which is set to 0.
Push all edges coming from the source node to a min heap.
Pop each edge from the min heap, one by one. Because it is a min heap, the edge is popped out is always the shortest one.
For each edge that is popped out, consider the target node. If the time coming from the source node to the target node through that edge is shorter than without it, update the time in minTimes, add all the edges coming from the target node to the min heap.
Continue step 3 and 4 until the min heap is empty.
Iterate throught the minTimes array from index 1 (because index 0 is the dummy one) to find the max value, if there is some element that still has Infinity value, that node hasn’t been reached yet. In this case, return -1.
Return the max value.

Revised by ChatGPT

Dijkstra's algorithm works by iteratively updating the shortest path to each node. Starting from the source node, it considers all outgoing edges and adds the shortest edge to the path. This process is repeated for each newly added node, considering all its outgoing edges. If a shorter path to a node is discovered, the algorithm updates the path length. This continues until all nodes have been considered. Here's an overview of the implementation:

Initialize a minTimes array to store the shortest time to reach each node, setting all elements to Infinity, except for the source node, which is set to 0.
Push all edges originating from the source node into a min-heap.
Pop the shortest edge from the min-heap and consider its target node. If the path through this edges to the target node is shorter than the current path, update the time in minTimes and add all edges originating from the target node to the min-heap.
Repeat step 3 until the min-heap is empty.
Iterate through the minTimes array to find the maximum value. If any element remains Infinity, it indicates that the corresponding node is unreachable, so return -1.
Return the maximum value, which represents the time required to reach the furthest node.