dijkstra堆优化
47. 参加科学大会（第六期模拟笔试） (kamacoder.com)
昨天对dijkstra算法有基本的认识，算法的时间复杂度为O(n^2)，也在昨天内容中提到过，使用优先队列（最小堆）能够将时间复杂度降为O(nlogn)，这里来讲述下如何实现。
未优化的dijkstra算法需要对每个节点进行遍历，这在稠密图中是必要的，但对于稀疏图则造成了很多资源的浪费，此外，需意识到如果知道了边，则自然知道了边连接的两个节点。我们将带权值的边加入到最小堆中，堆顶就是距离源点最近的节点所在的边。这里我们详细描述下这句话。
- 小顶堆的特点是堆顶元素是堆中最小的元素。
- 小顶堆会根据边的权值进行排序，权值最小的边会排在堆顶。
- 在算法的迭代过程中，我们每次都从小顶堆的堆顶取出一条边，由于堆的性质，这条边必然是所有未处理边中权值最小的。
- 当我们取出一条边时，这条边的一个端点是已经确定最短路径的节点，另一个端点是需要处理的节点，因为这条边的权值最小，可以认为通过这条边到达的节点是目前未处理节点中距离源点最近的。
使用邻接链表的方式构造图。
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std;
// 自定义比较类，用于优先队列，使得优先队列按照pair的第二个元素从小到大排序
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
// 如果lhs的第二个元素大于rhs的第二个元素，则lhs的优先级低于rhs
return lhs.second > rhs.second;
}
};
// 边的结构体，表示图中的一条边，包含目标节点和边的权值
struct Edge {
int to; // 边的目标节点
int val; // 边的权值
Edge(int t, int w) : to(t), val(w) {} // 构造函数
};
int main() {
int n, m; // n为节点数，m为边数
cin >> n >> m; // 输入节点数和边数
// 创建一个邻接表来表示图，grid[i]表示节点i的所有出边
vector<list<Edge>> grid(n + 1);
int p1, p2, val;
// 读取所有边的信息，并构建图
for (int i = 0; i < m; i++) {
cin >> p1 >> p2 >> val; // 输入边的信息，p1为起点，p2为终点，val为权值
grid[p1].push_back(Edge(p2, val)); // 将边添加到邻接表中
}
int start = 1; // 起始节点
int end = n; // 终止节点
// 初始化最小距离数组，所有节点的最小距离初始为INT_MAX
vector<int> minDist(n + 1, INT_MAX);
// 初始化访问标记数组，所有节点初始为未访问
vector<int> visited(n + 1, 0);
// 创建一个优先队列，用于存储节点和对应的最短距离
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;
// 将起始节点和距离0（起始节点到自身的距离）加入优先队列
pq.push(pair<int, int>(start, 0));
// 起始节点的最小距离设置为0
minDist[start] = 0;
// 当优先队列不为空时，进行处理
while (!pq.empty()) {
// 取出优先队列中距离最小的节点
pair<int, int> cur = pq.top();
pq.pop();
// 如果当前节点已经被访问过，则跳过
if (visited[cur.first]) continue;
// 标记当前节点为已访问
visited[cur.first] = 1;
// 遍历当前节点的所有出边
for (Edge edge : grid[cur.first]) {
// 如果目标节点未被访问且通过当前节点到达目标节点的距离更短
if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) {
// 更新目标节点的最小距离
minDist[edge.to] = minDist[cur.first] + edge.val;
// 将更新后的节点和距离加入优先队列
pq.push(pair<int, int>(edge.to, minDist[edge.to]));
}
}
}
// 如果终止节点的最小距离仍然是INT_MAX，说明无法到达终止节点
if (minDist[end] == INT_MAX) cout << -1 << endl;
// 否则，输出到达终止节点的最短路径长度
else cout << minDist[end] << endl;
return 0;
}
算法的时间复杂度
- 初始化：将所有节点加入优先队列，这一步的时间复杂度是O(V)，其中V是节点的数量。
- 主循环：每次从优先队列中提取最小元素，并将其所有邻接边加入优先队列。优先队列中每次操作（插入和删除最小元素）的时间复杂度是O(log V)，并且每个节点最多只会被加入和删除一次。因此，主循环的时间复杂度是O(V * log V)。
- 更新邻接节点：对于每个节点，我们可能需要遍历其所有邻接节点，这需要O(E)时间，其中E是边的数量。
总的时间复杂度为O((V+E)*logV)，通常情况下简化为O(E*logV)
空间复杂度
- 邻接表：用于存储图的空间复杂度是O(V + E)，因为我们需要存储每个节点以及它们之间的边。
- 最小距离数组
minDist：空间复杂度是O(V)，用于存储每个节点到源点的最短距离。 - 访问标记数组
visited：空间复杂度是O(V)，用于标记节点是否被访问过。 - 优先队列：在最坏的情况下，所有节点都可能被加入优先队列，因此空间复杂度是O(V)。
总的空间复杂度是O(V + E)，这是由邻接表和辅助数据结构（如minDist和visited数组）共同决定的。
Bellman-ford算法
之前提到过dijktra算法不能处理含负权值的图，Bellman-ford算法可以处理包含负权边的图。
Bellman-ford算法的基本步骤如下：
初始化：
- 创建一个距离数组min_Dist
[]，对于每一个节点v，min_Dist[v]的值被设置为无穷大，表示源点到节点v的距离是未知的，只有min_Dist[source]被设置为0，因为源点到自身的距离是0。 - 创建一个前驱数组
pred[]，用于存储最短路径中每个节点的前一个节点。
- 创建一个距离数组min_Dist
松弛操作：
- 对图中的每一条边进行
|V|-1次松弛操作，其中|V|是图中节点的数量。松弛操作指的是对于每一条边u -> v，如果dist[u] + weight(u, v) < dist[v]，则更新dist[v]为dist[u] + weight(u, v)，同时更新pred[v]为u。 - 每松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离（参考代码随想录），所以若节点为v，则松弛v-1次就能得到起点1到终点v的最短距离。
- 对图中的每一条边进行
检测负权重循环：
- 在完成了
|V|-1次松弛操作之后，对所有的边再进行一次检查。如果还可以继续松弛，即存在dist[u] + weight(u, v) < dist[v]的情况，则说明图中存在负权重循环，因为经过|V|-1次松弛后所有最短路径都应该已经找到了。
- 在完成了
模拟过程参考代码随想录 代码随想录 (programmercarl.com)
Bellman-Ford算法的特点
- 能够处理负权边：这是Bellman-Ford算法与Dijkstra算法的主要区别之一。
- 能够检测负权重循环：如果图中存在负权重循环，则不存在最短路径，因为可以无限次地绕着负权重循环行走，使路径权重无限小。
- 时间复杂度：Bellman-Ford算法的时间复杂度是
O(|V||E|)，其中|V|是顶点数，|E|是边数。
伪代码
function Bellman-Ford(graph, source):
// 初始化距离数组和前驱数组
for each vertex v in graph.Vertices:
dist[v] := INFINITY // 将所有节点的距离设置为无穷大
pred[v] := NULL // 将所有节点的前驱设置为NULL
dist[source] := 0 // 源点到自身的距离设置为0
// 进行|V|-1次松弛操作，|V|是顶点数
for i from 1 to graph.Vertices.Count - 1:
for each edge (u, v) in graph.Edges:
// 如果通过边u->v能够找到更短的路径到v
if dist[u] + edge.Weight < dist[v]:
// 更新v的距离
dist[v] := dist[u] + edge.Weight
// 更新v的前驱节点为u
pred[v] := u
// 检测图中是否存在负权重循环
for each edge (u, v) in graph.Edges:
// 如果在完成所有松弛操作后还能继续松弛
if dist[u] + edge.Weight < dist[v]:
// 报错，说明图中存在负权重循环
error "Graph contains a negative-weight cycle"
// 返回距离数组和前驱数组
return (dist[], pred[])
对本题，不需要pred数组，因为只需要知道最短值即可，代码
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, m; // n是顶点数，m是边数
cin >> n >> m; // 读取顶点数和边数
vector<vector<int>> grid; // 创建一个二维向量来存储图的所有边
int p1, p2, val;
for (int i = 0; i < m; i++) {
cin >> p1 >> p2 >> val; // 读取每条边的起点、终点和权重
grid.push_back({p1, p2, val}); // 将边添加到grid中
}
int start = 1; // 起始顶点编号
int end = n; // 终止顶点编号
vector<int> min_Dist(n + 1, INT_MAX); // 创建距离数组，初始化为无穷大
min_Dist[1] = 0; // 起始顶点到自身的距离为0
// 进行n-1次松弛操作
for (int i = 1; i < n; i++) {
for (auto &vec : grid) {
int from = vec[0]; // 边的起点
int to = vec[1]; // 边的终点
int val = vec[2]; // 边的权重
// 如果起点可达且通过当前边可以找到更短的路径到终点
if (min_Dist[from] != INT_MAX && min_Dist[to] > min_Dist[from] + val) {
min_Dist[to] = min_Dist[from] + val; // 更新终点的最短距离
}
}
}
// 检查终止顶点是否可达
if (min_Dist[n] == INT_MAX)
cout << "unconnected" << endl; // 如果不可达，输出unconnected
else
cout << min_Dist[n] << endl; // 否则输出最短距离
return 0;
}
算法的时间复杂度为O(n*m)，空间复杂度为O(n+m)
