【CS.AL】算法核心之贪心算法 —— 力扣(LeetCode)743. 网络延迟时间 - Dijkstra算法题解

题目描述

743. 网络延迟时间 - 力扣（LeetCode）

有 N 个网络节点，标记为 1 到 N。

给定一个列表 times，其中 times[i] = (u, v, w) 表示有一条从节点 u 到节点 v 的时延为 w 的有向边。

现在，我们从某个节点 K 发送一个信号。需要多少时间才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

示例:

输入: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
输出: 2

可以使用 Dijkstra 算法来解决这个问题。算法的步骤如下：

1. 构建邻接表：将输入的 times 转换成图的邻接表表示。 Ref. 【CS.DS】数据结构 —— 图：深入了解三种表示方法之邻接表(Adjacency List)
2. 初始化数据结构：距离数组 dist[]，所有节点的距离初始化为无穷大，起点的距离设为 0；优先级队列 pq 存储每个节点及其当前已知的最短距离。
3. 执行 Dijkstra 算法：使用优先级队列选择当前距离起点最近的节点，更新其邻接节点的距离，并将更新后的节点加入队列。
4. 计算结果：在所有节点都收到信号时，返回最大的距离；如果有节点未收到信号，返回 -1。

#include <vector>
#include <unordered_map>
#include <queue>
#include <climits>using namespace std;int networkDelayTime(vector<vector<int>>& times, int N, int K) {// 构建图的邻接表unordered_map<int, vector<pair<int, int>>> graph;for (const auto& time : times) {int u = time[0], v = time[1], w = time[2];graph[u].emplace_back(v, w);}// 初始化距离表vector<int> dist(N + 1, INT_MAX);dist[K] = 0;// 优先队列，按距离从小到大排序priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;pq.emplace(0, K);while (!pq.empty()) {auto [current_dist, u] = pq.top();pq.pop();if (current_dist > dist[u]) {continue;}for (const auto& [v, w] : graph[u]) {int distance = current_dist + w;if (distance < dist[v]) {dist[v] = distance;pq.emplace(distance, v);}}}int max_dist = 0;for (int i = 1; i <= N; ++i) {if (dist[i] == INT_MAX) {return -1;}max_dist = max(max_dist, dist[i]);}return max_dist;
}int main() {vector<vector<int>> times = {{2,1,1},{2,3,1},{3,4,1}};int N = 4;int K = 2;int result = networkDelayTime(times, N, K);if (result == -1) {cout << "无法使所有节点都收到信号" << endl;} else {cout << "所有节点都收到信号所需的时间: " << result << endl;}return 0;
}

• 构建图的邻接表：
  • 我们使用 unordered_map 将每个节点的邻接节点及其权重存储起来。
• 初始化距离数组和优先级队列：
  • 距离数组 dist 用于记录从起点到每个节点的最短距离，初始时所有距离设为无穷大，起点的距离设为 0。
  • 优先级队列 pq 用于高效选择当前距离最短的节点，初始时将起点入队。
• Dijkstra 算法：
  • 每次从优先级队列中取出距离最短的节点，更新其邻接节点的距离，并将更新后的节点加入队列。
• 计算结果：
  • 遍历距离数组，找到所有节点中最大的距离作为结果。如果有节点的距离仍为无穷大，返回 -1。

References

• 【CS.AL】算法核心之贪心算法：从入门到进阶
  
• 【CS.DS】数据结构 —— 图：深入了解三种表示方法之邻接表(Adjacency List)
• 【CS.AL】算法核心之贪心算法：从入门到进阶