算法题 网络延迟时间

网络延迟时间

问题描述

有n个网络节点，标记为1到n。
给你一个列表times，表示信号经过有向边的传递时间：times[i] = (ui, vi, wi)，其中ui是源节点，vi是目标节点，wi是一个信号从源节点传递到目标节点的时间。

现在，从某个节点k发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回-1。

示例：

输入: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 输出: 2

算法思路

经典的单源最短路径问题，可以使用Dijkstra算法解决。

Dijkstra算法核心思想：

1. 维护一个距离数组dist，记录从起始节点到每个节点的最短距离
2. 使用优先队列（最小堆）选择当前距离最短的未处理节点
3. 对选中的节点，更新其邻居节点的距离
4. 重复直到处理完所有可达节点

关键：

1. 建图：将输入的边列表转换为邻接表表示
2. 初始化：起始节点距离为0，其他节点距离为无穷大
3. 松弛操作：通过当前节点更新邻居节点的最短距离
4. 结果计算：找到所有节点中的最大距离，如果有节点不可达则返回-1

代码实现

方法一：Dijkstra算法

importjava.util.*;classSolution{/** * 计算从节点k发出信号到达所有节点所需的最长时间 * * @param times 有向边列表，每个元素为[源节点, 目标节点, 权重] * @param n 网络节点总数（节点编号1到n） * @param k 信号起始节点 * @return 所有节点收到信号的最短时间，如果无法到达所有节点返回-1 */publicintnetworkDelayTime(int[][]times,intn,intk){// 1: 构建邻接表表示的图// graph[i] 存储从节点i出发的所有边，每个边用[目标节点, 权重]表示List<int[]>[]graph=newList[n+1];for(inti=1;i<=n;i++){graph[i]=newArrayList<>();}// 填充邻接表for(int[]edge:times){intu=edge[0],v=edge[1],w=edge[2];graph[u].add(newint[]{v,w});}// 2: 初始化距离数组// dist[i] 表示从起始节点k到节点i的最短距离int[]dist=newint[n+1];Arrays.fill(dist,Integer.MAX_VALUE);dist[k]=0;// 起始节点到自身的距离为0// 3: 使用优先队列实现Dijkstra算法// 优先队列存储[节点, 距离]，按距离从小到大排序PriorityQueue<int[]>pq=newPriorityQueue<>((a,b)->a[1]-b[1]);pq.offer(newint[]{k,0});// 记录已处理的节点数量boolean[]visited=newboolean[n+1];while(!pq.isEmpty()){int[]current=pq.poll();intnode=current[0];intdistance=current[1];// 如果当前节点已经处理过，跳过（处理重复入队的情况）if(visited[node]){continue;}visited[node]=true;// 遍历当前节点的所有邻居for(int[]neighbor:graph[node]){intnextNode=neighbor[0];intweight=neighbor[1];// 如果通过当前节点到达邻居的距离更短，则更新if(dist[node]+weight<dist[nextNode]){dist[nextNode]=dist[node]+weight;pq.offer(newint[]{nextNode,dist[nextNode]});}}}// 4: 计算结果intmaxTime=0;for(inti=1;i<=n;i++){// 如果存在节点不可达，返回-1if(dist[i]==Integer.MAX_VALUE){return-1;}maxTime=Math.max(maxTime,dist[i]);}returnmaxTime;}}

算法分析

• 时间复杂度：O((V + E) log V)

  • V = n（节点数），E = times.length（边数）
  • 每个节点最多入队一次，每次堆操作O(log V)
  • 每条边最多被处理一次

• 空间复杂度：O(V + E)

  • 邻接表存储：O(V + E)
  • 距离数组：O(V)
  • 优先队列：O(V)

算法过程

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

初始化：

• 邻接表：graph[2] = [[1,1], [3,1]],graph[3] = [[4,1]]
• 距离数组：dist = [∞, ∞, 0, ∞, ∞]（索引0不使用）
• 优先队列：[(2, 0)]

执行过程：

1. 处理节点2（距离0）：

   • 更新节点1：dist[1] = 0 + 1 = 1
   • 更新节点3：dist[3] = 0 + 1 = 1
   • 队列：[(1,1), (3,1)]

2. 处理节点1（距离1）：

   • 节点1无出边
   • 队列：[(3,1)]

3. 处理节点3（距离1）：

   • 更新节点4：dist[4] = 1 + 1 = 2
   • 队列：[(4,2)]

4. 处理节点4（距离2）：

   • 节点4无出边
   • 队列为空

最终距离：dist = [∞, 1, 0, 1, 2]
最大距离：max(1, 0, 1, 2) = 2

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[][]times1={{2,1,1},{2,3,1},{3,4,1}};System.out.println("Test 1: "+solution.networkDelayTime(times1,4,2));// 2// 测试用例2：无法到达所有节点int[][]times2={{1,2,1}};System.out.println("Test 2: "+solution.networkDelayTime(times2,2,2));// -1// 测试用例3：单个节点int[][]times3={};System.out.println("Test 3: "+solution.networkDelayTime(times3,1,1));// 0// 测试用例4：复杂网络int[][]times4={{1,2,1},{2,3,2},{1,3,4}};System.out.println("Test 4: "+solution.networkDelayTime(times4,3,1));// 3// 测试用例5：包含环路但不影响最短路径int[][]times5={{1,2,1},{2,1,3},{2,3,2},{3,4,1}};System.out.println("Test 5: "+solution.networkDelayTime(times5,4,1));// 4// 测试用例6：大权重边int[][]times6={{1,2,100},{2,3,100},{3,4,100}};System.out.println("Test 6: "+solution.networkDelayTime(times6,4,1));// 300// 测试用例7：多条路径到同一节点int[][]times7={{1,2,1},{1,3,4},{2,3,2},{2,4,6},{3,4,3}};System.out.println("Test 7: "+solution.networkDelayTime(times7,4,1));// 6}

关键点

1. 图：

   • 使用邻接表而非邻接矩阵，节省空间
   • 邻接表索引从1开始，对应节点编号

2. 优先队列：

   • 始终选择当前距离最短的未处理节点
   • 保证每次处理的都是最优解（贪心策略）

3. 重复入队处理：

   • 同一节点可能多次入队（距离更新时）
   • 通过visited数组或距离比较避免重复处理

4. 不可达节点：

   • 距离仍为Integer.MAX_VALUE表示不可达
   • 只要有1个不可达节点就返回-1

5. 结果：

   • 需要所有节点都收到信号，所以取最大距离
   • 起始节点自身距离为0，不影响结果

常见问题

1. 为什么使用Dijkstra而不是其他最短路径算法？

   • 传递时间都是正数，Dijkstra最适合
   • 如果有权重为负的情况，需要使用Bellman-Ford

2. visited数组？

   • 使用visited数组可以减少堆操作次数，提高效率

3. 如何处理节点编号从1开始？

   • 创建大小为n+1的数组，忽略索引0