最短路
单源最短路
Bellman-Ford 算法
Bellman-Ford 算法可以处理负权边, 它通过对边进行松弛操作来渐进的降低从源节点 到每个节点 的最短路径的估计值 , 直到该估计值与实际的最短路径权重 相同时为止。 该算法返回值为 True 当且仅当输入图不包含可以从源节点到达的权重为负值的环路。
可以判是否存在负权环
但注意， 单次只能判断是否存在从源点可达的负权环
伪代码
由于算法第 1 行的初始化操作所需时间为 , 第 2-4 行循环的运行时间为 , 且一共要进行 次循环， 第 5-7 行的 for 循环的所需时间为 , Bellman-Ford 算法的总运行时间为 O(VE)
BellmanFord(G, w, s)
d[s]←0 // 初始化，s到s最短路权值为0，其他为正无穷
for each v∈V-{s}
d[v]←∞
parent[v]← NIL // 为生成最短路径树起作用
// 最多只需|V|-1次外层循环，|V|-1次结束后，若图G中无负权回路，那么s到其他所有顶点的最短路径求得
// 且这里的循环次数有实际意义， 表示当前源点s到每个点的最短距离经过不超过i条边
for i ← 1 to |V|-1
for each edge (u, v)∈E // 算法核心，松弛每一条边，维持三角不等式成立
if d[v] > d[u] + w(u, v)
d[v] ← d[u]+w(u, v)
parent[v]←u // 边(u,v)松弛成功，则u为v的前驱顶点，记录到parent[]
// 进行完|V|-1次循环操作后，如果还能某条边还能进行松弛，说明到某个点的最短路径还未找到，那么必定是存在负权回路，返回FALSE
for each edge (u, v)∈E
if d[v] > d[u] + w(u, v)
return FALSE
return TRUE
// 若进行上面的松弛之后没有返回，说明所有的d值都不会再改变了，那么最短路径权值完全找到，返回TRUE
Dijkstra 算法
正确性证明
伪代码
实现
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<vector<pair<int, int>>> edges;
vector<int> dis, vis;
void dijkstra(int s) {
priority_queue<pair<int, int>, vector<pair<int, int>>,
greater<pair<int, int>>>
pq;
dis[s] = 0;
pq.emplace(dis[s], s);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (vis[u] == 0) {
vis[u] = 1;
for (auto &[v, w] : edges[u]) {
if (vis[v] == 0 && d + w < dis[v]) {
dis[v] = d + w;
pq.emplace(dis[v], v);
}
}
}
}
}
int main() {
int n, m, s, u, v, w;
cin >> n >> m >> s;
edges.resize(n + 1);
dis.resize(n + 1, INT32_MAX);
vis.resize(n + 1, 0);
for (int i = 0; i < m; ++i) {
cin >> u >> v >> w;
edges[u].emplace_back(v, w);
}
dijkstra(s);
for (int i = 1; i <= n; ++i) {
cout << dis[i] << " ";
}
cout << endl;
return 0;
}
为什么Dijkstra算法不能求解带负权图的最短路径？
因为 Dijktra 算法每一次将一个节点加入已访问集合之中，之后不能再更新， 那么如果出现了如下的情况
算法刚开始执行时，将 A 添加到集合中标记已访问，之后选出从A到所有节点中的最短的 ，于是把C加入集合中标记已访问，之后 C 不能在更新了，而显然，A与C之间最短路径权值为0（A-B-C），发生错误。