最短路题目：网络延迟时间-平芜编程栈

文章目录

题目
- 标题和出处
- 难度
- 题目描述
- - 要求
  - 示例
  - 数据范围
前言
解法一
- 思路和算法
- 代码
- 复杂度分析
解法二
- 思路和算法
- 代码
- 复杂度分析

题目

标题和出处

标题：网络延迟时间

出处：743. 网络延迟时间

难度

5 级

题目描述

要求

给定一个由n \texttt{n}n个结点组成的网络，结点编号为1 \texttt{1}1到n \texttt{n}n。另外给定一个表示信号经过有向边的传递时间的列表times \texttt{times}times，times[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≤100
1 ≤ times.length ≤ 6000 \texttt{1} \le \texttt{times.length} \le \texttt{6000}1≤times.length≤6000
times[i].length = 3 \texttt{times[i].length} = \texttt{3}times[i].length=3
1 ≤ u i , v i ≤ n \texttt{1} \le \texttt{u}_\texttt{i}\texttt{, v}_\texttt{i} \le \texttt{n}1≤ui, vi≤n
u 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]=0，receiveTimes \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[]receiveTimes=newint[n+1];Arrays.fill(receiveTimes,Integer.MAX_VALUE);receiveTimes[0]=receiveTimes[k]=0;for(inti=1;i<n;i++){for(int[]edge:times){intstart=edge[0],end=edge[1],weight=edge[2];if(receiveTimes[start]!=Integer.MAX_VALUE&&receiveTimes[end]>receiveTimes[start]+weight){receiveTimes[end]=receiveTimes[start]+weight;}}}intmaxTime=Arrays.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){List<int[]>[]adjacentArr=newList[n+1];for(inti=0;i<=n;i++){adjacentArr[i]=newArrayList<int[]>();}for(int[]edge:times){intstart=edge[0],end=edge[1],weight=edge[2];adjacentArr[start].add(newint[]{end,weight});}int[]receiveTimes=newint[n+1];Arrays.fill(receiveTimes,Integer.MAX_VALUE);receiveTimes[0]=receiveTimes[k]=0;boolean[]visited=newboolean[n+1];for(inti=1;i<=n;i++){intcurr=-1;for(intj=1;j<=n;j++){if(!visited[j]&&(curr<0||receiveTimes[curr]>receiveTimes[j])){curr=j;}}visited[curr]=true;for(int[]adjacent:adjacentArr[curr]){intnext=adjacent[0],weight=adjacent[1];receiveTimes[next]=Math.min(receiveTimes[next],receiveTimes[curr]+weight);}}intmaxTime=Arrays.stream(receiveTimes).max().getAsInt();returnmaxTime!=Integer.MAX_VALUE?maxTime:-1;}}

下面的代码为基于小根堆实现。

classSolution{publicintnetworkDelayTime(int[][]times,intn,intk){List<int[]>[]adjacentArr=newList[n+1];for(inti=0;i<=n;i++){adjacentArr[i]=newArrayList<int[]>();}for(int[]edge:times){intstart=edge[0],end=edge[1],weight=edge[2];adjacentArr[start].add(newint[]{end,weight});}int[]receiveTimes=newint[n+1];Arrays.fill(receiveTimes,Integer.MAX_VALUE);receiveTimes[0]=receiveTimes[k]=0;PriorityQueue<int[]>pq=newPriorityQueue<int[]>((a,b)->a[1]-b[1]);pq.offer(newint[]{k,0});while(!pq.isEmpty()){int[]pair=pq.poll();intcurr=pair[0],receiveTime=pair[1];if(receiveTimes[curr]<receiveTime){continue;}for(int[]adjacent:adjacentArr[curr]){intnext=adjacent[0],weight=adjacent[1];if(receiveTimes[next]>receiveTime+weight){receiveTimes[next]=receiveTime+weight;pq.offer(newint[]{next,receiveTimes[next]});}}}intmaxTime=Arrays.stream(receiveTimes).max().getAsInt();returnmaxTime!=Integer.MAX_VALUE?maxTime:-1;}}

复杂度分析

时间复杂度：O ( n 2 + m ) O(n^2 + m)O(n2+m)或O ( ( n + m ) log ⁡ n ) O((n + m) \log n)O((n+m)logn)，其中n nn是图中的结点数，m mm是图中的边数。将边数组转换成邻接结点列表需要O ( n + m ) O(n + m)O(n+m)的时间，Dijkstra 算法的时间复杂度取决于实现方式，基于枚举实现的时间复杂度是O ( n 2 ) O(n^2)O(n2)，基于小根堆实现的时间复杂度是O ( ( n + m ) log ⁡ n ) O((n + m) \log n)O((n+m)logn)，计算所有结点的最短路径权重需要O ( n ) O(n)O(n)的时间得到使所有结点都收到信号的最少时间，因此时间复杂度是O ( n 2 + m ) O(n^2 + m)O(n2+m)或O ( ( n + m ) log ⁡ n ) O((n + m) \log n)O((n+m)logn)。
空间复杂度：O ( n + m ) O(n + m)O(n+m)，其中n nn是图中的结点数，m mm是图中的边数。邻接结点列表需要O ( n + m ) O(n + m)O(n+m)的空间，记录从结点k kk到每个结点的最短路径需要O ( n ) O(n)O(n)的空间，记录每个结点是否访问过的数组和优先队列需要O ( n ) O(n)O(n)的空间，因此空间复杂度是O ( n + m ) O(n + m)O(n+m)。