743. Network Delay Time - Dijkstra's Algorithm

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;
    }
}

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 is discovered to a node, the algorithm updates the path length. This continues until all nodes have been considered.

Here's an overview of the implementation:

1. 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.
2. Push all edges originating from the source node into a min-heap.
3. Pop the shortest edge from the min-heap and consider its target node. If the path through this edge 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.
4. Repeat step 3 until the min-heap is empty.
5. 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.
6. Return the maximum value, representing the time required to reach the furthest node.