743. Network Delay Time
Question
You are given a network of
n
nodes, labeled from1
ton
. You are also giventimes
, a list of travel times as directed edgestimes[i] = (u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>)
, whereu<sub>i</sub>
is the source node,v<sub>i</sub>
is the target node, andw<sub>i</sub>
is the time it takes for a signal to travel from source to target.We will send a signal from a given node
k
. Return the time it takes for all then
nodes to receive the signal. If it is impossible for all then
nodes to receive the signal, return-1
.
Solution
Dijkstra算法
此题可以转化为求起始节点到最远距离的节点的距离。单源最短路径问题,可以采用Dijkstra算法。
采用一个visited[]数组记录初始节点的访问状况。
同时dist[]数组记录到达这一节点的最小距离,初始化为无限大。
进行BFS搜索,每次优先访问当前节点的子节点的最近子节点,并更新子节点与初始节点距离。
最后遍历dist[]数组,如果有元素仍为无限大,则BFS搜索未遍历到,返回-1。
否则返回数组内最大的距离即可。
建立映射
首先通过哈希表,将起始节点与有向边建立起映射关系。列表中储存子节点和对应边上的权值。
注意由于index是-1的,因此在组成列表时需要将当前数字减一。
优先级队列
采用优先级队列组成小根堆,每次将当前的最小距离作为权值加入队列。
初始化队列时需要将起始节点(k-1)放入,此时的总距离为0。
当当前的子节点的cost加上起始节点的距离小于子节点的最小距离时,更新子节点最小距离。
同时将子节点当前最小距离作为比较对象传入优先级队列。
Code
1 | class Solution { |
743. Network Delay Time
https://xuanhe95.github.io/2022/05/15/743-Network-Delay-Time/