核心思想
- 所有的点分类两类 $\text{A}$ (已经根据此集合中的点去更新其他点的距离), $\text{B}$ (未根据此集合中的点去更新其他点的距离)
- $\text{A}$ 和 $\text{B}$ 虽然是两个集合, 代码中可以用一个
vector<bool>数组实现 - 每次从 $\text{B}$ 中取一个最小的, 取更新其他点的距离
- $\text{B}$ 中的点为空, 遍历结束
局限性
在 $\text{Dijkstra}$ 算法的应用过程中, 某些有权图的边可能为负, 也就是说, 即使有权图中并不包含可以从节点到达的负权回路, $\text{Dijkstra}$ 算法依然是可以继续应用的, 但是假如存在一个可以直接从节点到达的负回路, 那么算法将无法进行操作, 最短路径的权也无法成立, 使得最短路径无法找到. 总而言之, 当有权图中出现了负权的话, $\text{Dijkstra}$ 算法就不成立了, 这也是该算法的最大缺陷.
优化
值得注意的是, 由于本题边数远大于点数, 是一张稠密图, 因此在运行时间上, 枚举写法要略快于堆的写法.
代码实现
枚举法
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
#define INF 0x3F3F3F3F
/**
* Dijkstra 算法的实现
* @param edges 图中的所有边
* @param n 途中所有的点, 编号从 1~n
* @param k 起始点
* @return 到各个点的最小距离
*/
vector<int> Dijkstra(vector<vector<int>> &edges, int n, int k) {
vector<vector<int>> g(n, vector<int>(n, INF)); // 邻接表 nxn 的矩阵, 其中的值是权重
for (auto &e: edges) { // 构建邻接表
int x = e[0] - 1;
int y = e[1] - 1;
g[x][y] = e[2];
}
vector<int> dist(n, INF); // k 到每个点的距离值
dist[k - 1] = 0; // k 到自己的值为 0
vector<int> used(n); // 节点是否已经访问了
for (int i = 0; i < n; ++i) { // 遍历 n 个点
int x = -1; // 没有使用的最小的顶点
for (int y = 0; y < n; ++y) { // 在 dist 中找没有使用的最小的顶点
if (! used[y] && (x == -1 || dist[y] < dist[x])) {
x = y;
}
}
used[x] = true; // 加入到 S 中
for (int y = 0; y < n; ++y) { // 遍历并更新其他点的距离
dist[y] = min(dist[y], dist[x] + g[x][y]);
}
}
return dist;
}使用堆优化
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 0x3F3F3F3F
vector<int> Dijkstra(vector<vector<int>> &edges, int n, int k) {
vector<vector<pair<int, int>>> g(n);
for (auto &e: edges) {
int x = e[0] - 1;
int y = e[1] - 1;
g[x].emplace_back(y, e[2]);
}
vector<int> dist(n, INF);
dist[k - 1] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
q.emplace(0, k - 1); // 将距离和点序号入列
while (! q.empty()) {
auto p = q.top();
q.pop();
int distance = p.first, x = p.second;
// 准备用来遍历的点比现在的点的距离还大, 就不适合用它来更新了
if (dist[x] < distance) {
continue;
}
// 用当前点 x 来更新邻接点的距离
for (auto &e: g[x]) {
int y = e.first, d = dist[x] + e.second;
if (d < dist[y]) {
dist[y] = d;
q.emplace(d, y);
}
}
}
return dist;
}882. 细分图中的可到达节点
class Solution {
public:
int reachableNodes(vector<vector<int>> &edges, int maxMoves, int n) {
const int INF = 0x3F3F3F3F;
vector<vector<int>> g(n, vector<int>(n, INF));
for (auto &e: edges) {
g[e[0]][e[1]] = e[2] + 1;
g[e[1]][e[0]] = e[2] + 1;
}
int res = 0;
vector<int> visited(n, 0);
queue<int> q;
vector<int> dist(n, 0);
q.push(0);
visited[0] = 1;
while (!q.empty()) {
int len = q.size();
for (int i = 0; i < len; ++i) {
int v = q.front();
if (visited[v] == 2) {
continue;
}
for (int j = 0; j < n; ++j) {
if (g[v][j] == INF) {
continue;
}
if (v == 0) {
res += min(maxMoves, g[v][j]) + 1; // 0 到 j 可以走多少步
g[v][j] = maxMoves - g[v][j]; // 还剩下多少步
} else {
if (g[0][v] > 0 && g[0][j] < 0) { // v 还有可用步数
int relax = max(g[0][j], g[0][v] - g[v][j]);
if (relax > g[0][j]) { // 如果 relax 大于 g[0][j], 说明通过 v 到 j 比 0 到 j 更近
res += relax - g[0][j];
g[0][j] = relax;
}
}
}
if (visited[j] == 0) {
visited[j] = 1;
q.push(j);
}
}
visited[v] = 2;
q.pop();
}
}
return res;
}
};官方题解中提到需要在 Dijkstra 过程中记录边的覆盖进度, 但这其实是不必要的. 我们完全可以把这两件事情分成两步来做.
- 由边集表示处理得到邻接表表示 (注意初始化边权重的时候要在 n 的基础上再加 1, 因为距离等于增加的节点数目加 1)
- 使用 Dijkstra 算法计算从 0 到所有节点的最短距离.
- 使用 C++ STL 的
priority_queue记录需要拓展的节点, 注意priority_queue默认是大根堆, 这里需要将比较函数设置为greater<>, 从而将其变成小根堆. - 使用
vis[N]数组记录每一节点是否已经被拓展过. 一个节点最多只能拓展一次.
- 使用 C++ STL 的
- 利用计算得到的最短距离
dist[N], 遍历边集 $edges$ 中的边. 对其中的任意一条边, 我们可以从其左端点 $u$ 覆盖, 也可以从其右端点 $v$ 覆盖, 最后总的覆盖数目
$$
cover=\min(n,\max(0,\min(dist[u]-M, n))+\max(0,\min(dist[v]-M, n)))
$$ - 上一步累加的是新增点的覆盖情况, 我们还需要进行一次对 $N$ 个顶点的遍历, 来确定原始的 $N$ 个顶点的覆盖情况.
作者:lucifer1004
链接:https://leetcode.cn/problems/reachable-nodes-in-subdivided-graph/solution/dijkstradan-yuan-zui-duan-lu-jing-bu-xu-yao-ji-lu-/
来源: 力扣 (LeetCode)
著作权归作者所有. 商业转载请联系作者获得授权, 非商业转载请注明出处.
文章评论