文章目录题目标题和出处难度题目描述要求示例数据范围前言解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目标题和出处标题网络延迟时间出处743. 网络延迟时间难度5 级题目描述要求给定一个由n \texttt{n}n个结点组成的网络结点编号为1 \texttt{1}1到n \texttt{n}n。另外给定一个表示信号经过有向边的传递时间的列表times \texttt{times}timestimes[i] (u i , v i , w i ) \texttt{times[i] (u}_\texttt{i}\texttt{, v}_\texttt{i}\texttt{, w}_\texttt{i}\texttt{)}times[i] (ui​, vi​, wi​)其中u i \texttt{u}_\texttt{i}ui​是源结点v i \texttt{v}_\texttt{i}vi​是目标结点w i \texttt{w}_\texttt{i}wi​是一个信号从源结点传递到目标结点的时间。从给定结点k \texttt{k}k发出一个信号。返回使所有n \texttt{n}n个结点都收到信号的最少时间。如果不能使所有n \texttt{n}n个结点都收到信号返回-1 \texttt{-1}-1。示例示例 1输入times [[2,1,1],[2,3,1],[3,4,1]], n 4, k 2 \texttt{times [[2,1,1],[2,3,1],[3,4,1]], n 4, k 2}times [[2,1,1],[2,3,1],[3,4,1]], n 4, k 2输出2 \texttt{2}2示例 2输入times [[1,2,1]], n 2, k 1 \texttt{times [[1,2,1]], n 2, k 1}times [[1,2,1]], n 2, k 1输出1 \texttt{1}1示例 3输入times [[1,2,1]], n 2, k 2 \texttt{times [[1,2,1]], n 2, k 2}times [[1,2,1]], n 2, k 2输出-1 \texttt{-1}-1数据范围1 ≤ k ≤ n ≤ 100 \texttt{1} \le \texttt{k} \le \texttt{n} \le \texttt{100}1≤k≤n≤1001 ≤ times.length ≤ 6000 \texttt{1} \le \texttt{times.length} \le \texttt{6000}1≤times.length≤6000times[i].length 3 \texttt{times[i].length} \texttt{3}times[i].length31 ≤ u i , v i ≤ n \texttt{1} \le \texttt{u}_\texttt{i}\texttt{, v}_\texttt{i} \le \texttt{n}1≤ui​, vi​≤nu i ≠ v i \texttt{u}_\texttt{i} \ne \texttt{v}_\texttt{i}ui​vi​0 ≤ w i ≤ 100 \texttt{0} \le \texttt{w}_\texttt{i} \le \texttt{100}0≤wi​≤100所有(u i , v i ) \texttt{(u}_\texttt{i}\texttt{, v}_\texttt{i}\texttt{)}(ui​, vi​)对各不相同即不含重复边前言这道题要求计算从网络中的给定结点k kk发出信号到所有结点都收到信号的最少时间。由于给定的网络是有向带权图因此这道题等价于计算从结点k kk到所有结点的最短路径权重。单源最短路径算法包括 Bellman-Ford 算法和 Dijkstra 算法。这道题中每条边的权重都非负因此 Bellman-Ford 算法和 Dijkstra 算法都可以使用。解法一思路和算法当图中有n nn个结点时Bellman-Ford 算法的做法是对图中的所有边执行n − 1 n - 1n−1次遍历得到从结点k kk到每个结点的最短路径权重。创建数组receiveTimes \textit{receiveTimes}receiveTimes记录从结点k kk到每个结点的最短路径权重初始时receiveTimes [ k ] 0 \textit{receiveTimes}[k] 0receiveTimes[k]0receiveTimes \textit{receiveTimes}receiveTimes中的其余元素都是∞ \infty∞。将遍历到的边的起点、终点和权重分别记为start \textit{start}start、end \textit{end}end和weight \textit{weight}weight如果receiveTimes [ start ] ≠ ∞ \textit{receiveTimes}[\textit{start}] \ne \inftyreceiveTimes[start]∞且receiveTimes [ end ] receiveTimes [ start ] weight \textit{receiveTimes}[\textit{end}] \textit{receiveTimes}[\textit{start}] \textit{weight}receiveTimes[end]receiveTimes[start]weight则将receiveTimes [ end ] \textit{receiveTimes}[\textit{end}]receiveTimes[end]的值更新为receiveTimes [ start ] weight \textit{receiveTimes}[\textit{start}] \textit{weight}receiveTimes[start]weight。初始时可以确定结点k kk对应的最短路径权重是0 00。每一次遍历之后可以确定图中的一个结点对应的最短路径权重n − 1 n - 1n−1次遍历之后即可得到从源结点到每个结点的最短路径权重。如果所有结点的最短路径权重都不是∞ \infty∞则所有结点都能收到信号返回最短路径权重的最大值。如果存在结点的最短路径权重是∞ \infty∞则∞ \infty∞对应的结点不能收到信号返回− 1 -1−1。代码classSolution{publicintnetworkDelayTime(int[][]times,intn,intk){int[]receiveTimesnewint[n1];Arrays.fill(receiveTimes,Integer.MAX_VALUE);receiveTimes[0]receiveTimes[k]0;for(inti1;in;i){for(int[]edge:times){intstartedge[0],endedge[1],weightedge[2];if(receiveTimes[start]!Integer.MAX_VALUEreceiveTimes[end]receiveTimes[start]weight){receiveTimes[end]receiveTimes[start]weight;}}}intmaxTimeArrays.stream(receiveTimes).max().getAsInt();returnmaxTime!Integer.MAX_VALUE?maxTime:-1;}}复杂度分析时间复杂度O ( n m ) O(nm)O(nm)其中n nn是图中的结点数m mm是图中的边数。Bellman-Ford 算法的时间复杂度是O ( n m ) O(nm)O(nm)计算所有结点的最短路径权重需要O ( n ) O(n)O(n)的时间得到使所有结点都收到信号的最少时间因此时间复杂度是O ( n m ) O(nm)O(nm)。空间复杂度O ( n ) O(n)O(n)其中n nn是图中的结点数。记录从结点k kk到每个结点的最短路径权重需要O ( n ) O(n)O(n)的空间。解法二思路和算法当图中有n nn个结点时Dijkstra 算法的做法是对图中的结点执行n nn次循环得到从源结点到每个结点的最短路径权重。每次循环时从尚未确定最短路径权重的结点中找到最短路径权重最小的结点将该结点的状态更新为确定最短路径权重并使用该结点的最短路径权重更新该结点的所有后继结点的最短路径权重。由于每次循环都能确定一个结点的最短路径权重因此经过n nn次循环之后即可得到每个结点的最短路径权重。寻找最短路径权重最小的结点有两种做法第一种做法是枚举所有尚未确定最短路径权重的结点第二种做法是维护小根堆。为了方便处理需要首先将边数组转换成邻接结点列表的形式转换后可以在O ( 1 ) O(1)O(1)时间获得一个结点的全部相邻结点。代码下面的代码为基于枚举实现。classSolution{publicintnetworkDelayTime(int[][]times,intn,intk){Listint[][]adjacentArrnewList[n1];for(inti0;in;i){adjacentArr[i]newArrayListint[]();}for(int[]edge:times){intstartedge[0],endedge[1],weightedge[2];adjacentArr[start].add(newint[]{end,weight});}int[]receiveTimesnewint[n1];Arrays.fill(receiveTimes,Integer.MAX_VALUE);receiveTimes[0]receiveTimes[k]0;boolean[]visitednewboolean[n1];for(inti1;in;i){intcurr-1;for(intj1;jn;j){if(!visited[j](curr0||receiveTimes[curr]receiveTimes[j])){currj;}}visited[curr]true;for(int[]adjacent:adjacentArr[curr]){intnextadjacent[0],weightadjacent[1];receiveTimes[next]Math.min(receiveTimes[next],receiveTimes[curr]weight);}}intmaxTimeArrays.stream(receiveTimes).max().getAsInt();returnmaxTime!Integer.MAX_VALUE?maxTime:-1;}}下面的代码为基于小根堆实现。classSolution{publicintnetworkDelayTime(int[][]times,intn,intk){Listint[][]adjacentArrnewList[n1];for(inti0;in;i){adjacentArr[i]newArrayListint[]();}for(int[]edge:times){intstartedge[0],endedge[1],weightedge[2];adjacentArr[start].add(newint[]{end,weight});}int[]receiveTimesnewint[n1];Arrays.fill(receiveTimes,Integer.MAX_VALUE);receiveTimes[0]receiveTimes[k]0;PriorityQueueint[]pqnewPriorityQueueint[]((a,b)-a[1]-b[1]);pq.offer(newint[]{k,0});while(!pq.isEmpty()){int[]pairpq.poll();intcurrpair[0],receiveTimepair[1];if(receiveTimes[curr]receiveTime){continue;}for(int[]adjacent:adjacentArr[curr]){intnextadjacent[0],weightadjacent[1];if(receiveTimes[next]receiveTimeweight){receiveTimes[next]receiveTimeweight;pq.offer(newint[]{next,receiveTimes[next]});}}}intmaxTimeArrays.stream(receiveTimes).max().getAsInt();returnmaxTime!Integer.MAX_VALUE?maxTime:-1;}}复杂度分析时间复杂度O ( n 2 m ) O(n^2 m)O(n2m)或O ( ( n m ) log ⁡ n ) O((n m) \log n)O((nm)logn)其中n nn是图中的结点数m mm是图中的边数。将边数组转换成邻接结点列表需要O ( n m ) O(n m)O(nm)的时间Dijkstra 算法的时间复杂度取决于实现方式基于枚举实现的时间复杂度是O ( n 2 ) O(n^2)O(n2)基于小根堆实现的时间复杂度是O ( ( n m ) log ⁡ n ) O((n m) \log n)O((nm)logn)计算所有结点的最短路径权重需要O ( n ) O(n)O(n)的时间得到使所有结点都收到信号的最少时间因此时间复杂度是O ( n 2 m ) O(n^2 m)O(n2m)或O ( ( n m ) log ⁡ n ) O((n m) \log n)O((nm)logn)。空间复杂度O ( n m ) O(n m)O(nm)其中n nn是图中的结点数m mm是图中的边数。邻接结点列表需要O ( n m ) O(n m)O(nm)的空间记录从结点k kk到每个结点的最短路径需要O ( n ) O(n)O(n)的空间记录每个结点是否访问过的数组和优先队列需要O ( n ) O(n)O(n)的空间因此空间复杂度是O ( n m ) O(n m)O(nm)。