LeetCode 网络延迟时间 - Dijkstra 算法

网络延迟时间- Dijkstra的算法

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的算法通过迭代更新到每个节点的最短路径来起作用。从源节点开始，它考虑了所有传出边缘，并将最短的边缘添加到路径中。考虑到所有外向的边缘，每个新添加的节点都重复此过程。如果发现较短的路径到节点，则该算法会更新路径长度。这一直持续到所有节点都被考虑为止。

这是实施的概述：

1. 初始化 minTimes 数组存储到达每个节点的最短时间，将所有元素设置为 Infinity ，除了设置为源节点 0 。
2. 将所有源自源节点的边缘推入一个分钟-堆。
3. 弹出最短的边缘-堆并考虑其目标节点。如果通过此边缘到目标节点的路径比当前路径短，请更新时间 minTimes 并将所有源自目标节点的边缘添加到最小值-堆。
4. 重复步骤3直到最小-堆是空的。
5. 迭代 minTimes 数组以找到最大值。如果保留任何元素 Infinity ，这表明相应的节点是无法到达的，所以返回-1。
6. 返回最大值，表示达到最远节点所需的时间。