单源最短路径问题: Dijkstra 算法
1.非负权图单源最短路径问题: 给定图, 给定起点和终点, 要求计算最短路径
2.一开始起点和所有的其他节点之间的最短路径都标记成 inf, 我们通过某个算法持续更新, 从起点到其他所有节点之间的 [当前最短距离], 直到所有的节点都被标记完了, 得到真正的起点到其他所有节点的最短距离
将所有的节点分成两类
1.已经确定从起点到当前点的最短路径的节点, 简称为 [已确定节点]
2.未确定从起点到当前点的最短路径的节点, 简称为 [未确定节点]
一开始从起点O到其余所有节点都设置的距离设置为 inf
每次从 [未确定节点] 中取一个与起点 O 距离最短的点 A
1.把它归类为 [已确定节点] A
2.[更新] 从起点O到其他所有 [未确定节点] 的距离: 假设B是其中一个 [未确定节点], 如果用起点 O 到节点 A 的最短路加上 AB, 也就是 dist(OA) + dist(AB) < dist(OB), 那么 dist(OB) = dist(OA) + dist(AB), 这种操作叫做 [松弛] 直到所有的点都被归类为 [已确定节点]
1.为什么这么 [更新] 得到的路径是最短的?
这里暗含的信息是: 每次选择 [未确定节点] 例如 B 时, 起点到 [未确定节点] B 的最短路径长度可以被确定: 因为我们已经利用了每个 [已确定节点] 更新过了当前, 无需再次更新; 而当前节点已经是所有 [未确定节点] 中与起点距离最短的点, 不可能被其他 [未确定节点] 更新, 所以当前的节点可以被归类为 [已确定节点]
2.我自己的理解上面这个 [更新操作] 得到的路径是最短的贪心方法为什么是正确的, 假设 O 可以邻接 A/B/C 三个节点, 分别是 2/3/4 距离, O 挑一个路径最短的节点挑到了 2 也就是对应 A, A 就可以唯一确定下来是最短的路径, 那么不可能是其他节点各种访问过去到A是更小的吗? 不可能, 如果存在某节点比如 O/C/A 这种是最小的, 那么 OC 之间的长度必然小于 2 才能使得 OCA 小于2; 所以这种每次选最小的这种操作就能够唯一确定下来这种 [已确定节点], 直到把所有的节点都完成更新
dijkstra总共有两个版本
1.稠密图 Dijkstra: 邻接矩阵存储, 逐步增加 [已确认节点] 的集合
2.稀疏图 Dijkstra: 邻接链表存储, 采用 bfs+小顶堆维护 [未确认节点] 的集合
743.网络延迟时间
有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例 1：输入：times = [
[2,1,1],[2,3,1],[3,4,1]
], n = 4, k = 2 输出：2示例 2：输入：times = [[1,2,1]], n = 2, k = 1 输出：1
示例 3：输入：times = [[1,2,1]], n = 2, k = 2 输出：-1
分析:
1.从 K 节点统计到所有节点的最短路径, 然后取其中最大的最短路径, 因此是个最短路径问题
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
const int inf = INT_MAX / 2;
// 邻接矩阵建图
vector<vector<int>> graph(n, vector<int>(n, inf));
// 还原下标从0开始的情况
for (vector<int>& t : times) {
int i = t[0] - 1;
int j = t[1] - 1;
graph[i][j] = t[2];
}
// 起点到每个点的距离数组
vector<int> dist(n, inf);
// 从起点开始设置距离
dist[k - 1] = 0;
// 是否访问过
vector<int> visited(n, false);
// 总共遍历n次, 每确定1个[已确定节点]
for (int i = 0; i < n; ++i) {
int nextNode = -1;
// 每次找到和当前节点[距离最小]且[未被确定]的点t
for (int j = 0; j < n; ++j) {
// 只找[未确定节点]
if (!visited[j]) {
// 先设置首个[未确定节点]
if (nextNode == -1) {
nextNode = j;
} else if (dist[j] < dist[nextNode]) {
nextNode = j;
}
}
}
// 标记点t为已确定节点
visited[nextNode] = true;
// 利用已确定节点t, 更新其他的节点的当前最小距离
for (int j = 0; j < n; ++j) {
dist[j] = min(dist[j], dist[nextNode] + graph[nextNode][j]);
}
}
int ans = *max_element(dist.begin(), dist.end());
return ans == inf ? -1 : ans;
}
};
存储结构上采用邻接链表, 更新方式上采用 BFS+边权重小顶堆 可以维护当前节点的多个邻接节点, 也就是未确定节点集合
class Solution {
public:
struct cmp {
bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
}
};
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
const int inf = INT_MAX / 2;
vector<vector<pair<int, int>>> graph(n);
// pair<adj_node, adj_weight>
for (vector<int>& t : times) {
int x = t[0] - 1;
int y = t[1] - 1;
int weight = t[2];
graph[x].emplace_back(y, weight);
}
vector<int> dist(n, inf);
dist[k - 1] = 0;
// 按照边权重从小到大排序的[未确定节点]的pair<cur_dist, node_idx>
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
q.emplace(0, k - 1);
while (!q.empty()) {
pair<int, int> p = q.top();
q.pop();
int weight = p.first;
int x = p.second;
// 如果到x的距离小于weight
if (dist[x] < weight) {
continue;
}
// 遍历所有的邻居节点
for (pair<int, int>& e : graph[x]) {
int d = dist[x] + e.second;
int y = e.first;
if (d < dist[y]) {
dist[y] = d;
q.emplace(d, y);
}
}
}
int ans = *max_element(dist.begin(), dist.end());
return ans == inf ? -1 : ans;
}
};
转载请注明来源, from goldandrabbit.github.io
