Floyd
核心逻辑：
1
2
3
4
|
for (auto k = 1; k <= n; ++k)
for (auto x = 1; x <= n; ++x)
for (auto y = 1; y <= n; ++y)
f[x][y] = std::min(f[x][y], f[x][k] + f[k][y]);
|
时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$
Bellman-Ford
用途
处理有负权边的单源最短路，作为负权边图 dijkstra 的替代方案。
时间复杂度 $O(mn)$。
实现
判负环
🔗 洛谷 P3385 【模板】负环
SPFA
用途
优先队列优化 Bellman-Ford 时间复杂度。
时间复杂度
实现
Dijkstra
被证明普遍最优了 :)
用途
求解 非负权图 上单源最短路径
实现
将所有点分为 已经确定最短路点集 $S$ (vis[u] = true) 和 未确定最短路点集 $T$ (vis[u] = false])。
初始化源点 $s$ 有 $dis(s) = 0$，其他 $dis(u) = +\infty$
然后重复操作：
- 从 $T$ 取最短路长度最小的点，移到 $S$
- 对刚刚被加进 $S$ 的点所有出边进行松弛
$T$ 为空时结束。
暴力
优先队列优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
template<typename T = unsigned long long>
struct DijkstraGraph {
struct Node {
size_t u;
T dis;
friend auto operator<(const Node& lhs, const Node& rhs) -> bool {
return lhs.dis < rhs.dis;
}
};
struct Edge {
size_t to;
T dis;
};
size_t size;
std::vector<std::forward_list<T>> edges;
std::vector<T> dis;
std::vector<bool> vis;
explicit DijkstraGraph(size_t n) :
size(n),
edges(n + 1),
dis(n + 1, std::numeric_limits<T>::max()),
vis(n + 1, false)
{}
// add_edges(...)
// ...
auto dijkstra(size_t s) -> void {
std::priority_queue<Node, std::vector<Node>, std::greater<Node>> q; // subset of $T$
dis[s] = 0;
q.push({ s, dis[s] });
while (!q.empty()) {
auto u = q.top().u;
q.pop();
if (vis[u]) continue;
vis[u] = true;
for (const auto& e : edges[u])
if (dis[e.to] > dis[u] + e.dis) {
dis[e.to] = dis[u] + e.dis;
q.push({ e.to, dis[e.to] });
}
}
}
};
|
时间复杂度 $O(m\log{m})$。
Jhonson 全源最短路
用途
任意图 の 全源最短路
实现
为解决负权边，对边重新标注：
$$
w’ = w + h_u - h_v
$$
联想势能进行记忆。
其中 $h_u$ 是零势能面(节点0) 到节点 $u$ 的最短路。