🦌鹿心雨的小窝🦌
🦌鹿心雨的小窝
coverPiccoverPic

Leetcode 743 Network Delay Time，单源最短路径问题的解法

Dijkstra 算法Bellman-Ford 算法最短路问题算法与数据结构

🎈思路

Leetcode 743 Network Delay Time，在一个网络节点组成的有n个点的加权有向图中，返回从给定某一节点k出发发送信号，所有节点都能收到信号的耗时，有无法到达的节点则返回 -1。

这里要求我们找到从k点出发，到其他所有点的最短路径的最大值，是一个单源的最短路问题。解决单源的最短路问题，如果无负权边，通常采用 Dijkstra 算法，如果有负向边，就采用 Bellman-Ford 算法。

🎆Dijkstra 算法

Dijkstra 算法不断遍历离起始点最近且未访问过的节点，对每个未访问过的节点，遍历已访问过的节点以获取该节点距离起始点的最短距离。

我们需要求出节点k到其余所有点的最短路，其中的最大值就是答案。若存在从k出发无法到达的点，则返回 −1。

值得注意的是，最后返回最大值无需搜索整个距离数组。我们遍历节点是从近到远的，因此，最后一个节点肯定是离起始点最远的，因此，只需记录最近一次遍历节点的距离，到最后作为结果返回。

rust
  1. impl Solution {
  2.     pub fn network_delay_time(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
  3.         const MAX: i32 = 114514; // 这题节点权重最大 100，随便定个数当 inf 吧
  4.         let n_usize = n as usize;
  5.         // 构造邻接矩阵
  6.         let mut adjacency_map = vec![vec![MAX; n_usize]; n_usize];
  7.         for t in &times {
  8.             adjacency_map[t[0] as usize - 1][t[1] as usize - 1] = t[2];
  9.         }
  10.         let basic_row = k as usize - 1;
  11.         // 直接在第 k - 1 行上更新状态
  12.         adjacency_map[basic_row][basic_row] = 0;
  13.         let mut visit = vec![false; n_usize];
  14.         let mut last_dist = 0; // 记录最近遍历的节点的距离
  15.         loop {
  16.             let mut idx = n_usize;
  17.             for (i, &v) in visit.iter().enumerate() {
  18.                 if !v && (idx == n_usize || (adjacency_map[basic_row][i] < adjacency_map[basic_row][idx])) {
  19.                     idx = i;
  20.                 }
  21.             }
  22.             if idx == n_usize {
  23.                 return last_dist;
  24.             }
  25.             if adjacency_map[basic_row][idx] >= MAX {
  26.                 return -1;
  27.             }
  28.             visit[idx] = true;
  29.             for i in 0..n_usize {
  30.                 let res = adjacency_map[basic_row][i].min(adjacency_map[basic_row][idx] + adjacency_map[idx][i]);
  31.                 adjacency_map[basic_row][i] = res;
  32.             }
  33.             last_dist = adjacency_map[basic_row][idx];
  34.         }
  35.     }
  36. }

可以看到，需要遍历所有节点，外层循环时间复杂度 O(n)O(n)，寻找最近节点和更新节点距离需要时间复杂度 O(n)O(n)，时间复杂度 O(n2)O(n^2)。需要构造邻接矩阵，空间复杂度 O(n2)O(n^2)

🎇堆优化的 Dijkstra 算法

当图是稀疏图时，使用堆优化的 Dijkstra 算法更快，时间复杂度 O((n+m)log⁡n)O((n + m)\log n)，空间复杂度 O(n+m)O(n+m)，mm 是边的数量。这里用堆排序代替线性地查找最近节点。

稀疏图就是…边比较少的图，具体怎么定义看使用场景，上面写的的朴素的 Dijkstra 时间复杂度大概是 O(2n2)O(2n^2)，堆优化的时间复杂度是 O((n+m)log⁡n)O((n + m)\log n)。就这里而言所以稀疏图和稠密图的界限大概在 m=(2n2log⁡n−n)m=(2n^2\log n - n) 处，这也不怎么准确，毕竟时间复杂度是省略了低阶项和系数的结果…

rust
  1. use std::collections::BinaryHeap;
  2. impl Solution {
  3.     pub fn network_delay_time(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
  4.         const MAX: i32 = 114514;
  5.         let n_usize = n as usize;
  6.         let mut adjacency_map = vec![vec![]; n_usize];
  7.         for t in &times {
  8.             adjacency_map[t[0] as usize - 1].push((t[1] as usize - 1, t[2]));
  9.         }
  10.         let mut dist = vec![MAX; n_usize];
  11.         let basic_row = k as usize - 1;
  12.         dist[basic_row] = 0;
  13.         let mut heap = BinaryHeap::new(); // 建立二叉堆
  14.         heap.push((0, basic_row));
  15.         let mut last_dist = 0; // 类似地，记录上次的节距离
  16.         let mut node_count = 0; // 记录遍历节点数，不足 n 个就说明有不可到达的点，返回 -1
  17.         while let Some((dist_min, x)) = heap.pop() {
  18.             if -dist_min > dist[x] {
  19.                 continue;
  20.             }
  21.             node_count += 1;
  22.             let len = adjacency_map[x].len();
  23.             for i in 0..len {
  24.                 let (y, weight) = adjacency_map[x][i];
  25.                 let new_dist = -dist_min + weight;
  26.                 if new_dist < dist[y] {
  27.                     dist[y] = new_dist;
  28.                     heap.push((-new_dist, y));
  29.                 }
  30.             }
  31.             last_dist = dist[x];
  32.         }
  33.         if (node_count < n) {
  34.             return -1;
  35.         }
  36.         return last_dist;
  37.     }
  38. }

✨Bellman-Ford 算法

Bellman-Ford 算法主要用于有负权的图，它的思想是对所有的边进行 n−1n-1 轮松弛操作，因为在一个含有 nn 个顶点的图中，任意两点之间的最短路径最多包含 n−1n-1 边。时间复杂度 O(mn)O(mn)，空间复杂度 O(m)O(m)，mm 是边数。

rust
  1. impl Solution {
  2.     pub fn network_delay_time(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
  3.         let MAX = 114514;
  4.         let mut dis = vec![MAX; n as usize];
  5.         dis[(k - 1) as usize] = 0;
  6.         let edge_count = times.len();
  7.         let (mut to, mut from, mut weight) = (vec![0; edge_count], vec![0; edge_count], vec![0; edge_count]);
  8.         for i in 0..edge_count {
  9.             let edge = &times[i as usize];
  10.             to[i as usize] = edge[1] - 1;
  11.             from[i as usize] = edge[0] - 1;
  12.             weight[i as usize] = edge[2];
  13.         }
  14.         for k in 0..n - 1 {
  15.             let mut changed = false;
  16.             for i in 0..edge_count {
  17.                 let rest = dis[from[i as usize] as usize] + weight[i as usize];
  18.                 if (dis[to[i as usize] as usize] > rest) {
  19.                     dis[to[i as usize] as usize] = rest;
  20.                     changed = true;
  21.                 }
  22.             }
  23.             if !changed {
  24.                 break;
  25.             }
  26.         }
  27.         let mut ans = 0;
  28.         for i in 0..n {
  29.             ans = if dis[i as usize] < ans { ans } else { dis[i as usize] };
  30.         }
  31.         return if ans < MAX { ans } else { -1 };
  32.     }
  33. }

🎁结语

解决单源的最短路问题，如果无负权边，通常采用 Dijkstra 算法，对于稀疏图，可以进行堆优化；如果有负向边，就采用 Bellman-Ford 算法。

参考
https://leetcode.cn/problems/network-delay-time/solutions/2668220/liang-chong-dijkstra-xie-fa-fu-ti-dan-py-ooe8/
https://leetcode.cn/problems/network-delay-time/solutions/2999961/tu-lun-bfs-liang-chong-dijkstra-floyd-be-cfdv/

上一篇：广义线性模型笔记
0 条评论未登录用户
Ctrl or + Enter 评论
粤ICP备2023133136号
🌸 Run