LeetCode 网络延迟时间 - Dijkstra 算法

本文主要是介绍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. 返回最大值，表示达到最远节点所需的时间。

这篇关于LeetCode 网络延迟时间 - Dijkstra 算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---