743.网络延迟时间

Problem: 743. 网络延迟时间

文章目录 思路解题方法复杂度Code

思路

有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。 显然这是一道dijkstra算法模板就可以解决的一道题目

解题方法

初始化一个图来表示网络。图中的每条边表示两个节点之间的直接连接，边上的权重表示信号从一个节点到另一个节点的时间。 初始化一个距离数组来跟踪信号从起始节点到达每个节点的最小时间。 使用优先队列来跟踪还未访问的距离最小的节点。 从初始节点开始，更新距离数组中每个邻居的距离。 将当前节点标记为已访问，并将所有未访问的邻居添加到优先队列中。 重复步骤4和5，直到所有节点都被访问。 距离数组中的最大值就是信号到达所有节点所需的时间。

复杂度

时间复杂度:

时间复杂度: O ( E log ⁡ E ) O(E \log E) O(ElogE)，其中E是图中的边的数量。这是因为每条边都被添加到优先队列一次并被移除一次。

空间复杂度:

空间复杂度: O ( N + E ) O(N + E) O(N+E)，其中N是节点的数量，E是边的数量。这是存储图、距离数组和访问数组所需的空间。

Code class Solution { public int networkDelayTime(int[][] times, int n, int k) { // 初始化图 List<List<int[]>> graph = new ArrayList<>(); for(int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } // 建图 for(int[] edges : times) { graph.get(edges[0]).add(new int[]{edges[1], edges[2]}); } int[] dis = new int[n + 1]; Arrays.fill(dis, Integer.MAX_VALUE); dis[k] = 0; boolean[] vis = new boolean[n + 1]; PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]); heap.add(new int[]{k, 0}); while(!heap.isEmpty()) { int u = heap.poll()[0]; if(vis[u]) continue; vis[u] = true; for(int[] edge : graph.get(u)) { int v = edge[0]; int w = edge[1]; if(!vis[v] && dis[u] + w < dis[v]) { dis[v] = dis[u] + w; heap.add(new int[]{v, dis[u] + w}); } } } int ans = Integer.MIN_VALUE; for(int i = 1; i <= n; i++) { if(dis[i] == Integer.MAX_VALUE) { return -1; } ans = Math.max(ans, dis[i]); } return ans; } }