Fifnmar edited 4 年，2 月前
下面是对我学习这个部分的一点小总结
我觉得，我学习最短路径这个部分的时候有点忘记了我之前定下来的方针：「先知其所以然，再探究背后思想」。我之所以这么说，是因为我想，前辈想出这些经典的算法已经耗费了大量的精力，我直接学习它，然后再揣摩背后的思想，其性价比要优于先自己苦想、再看经典方法。学习图算法的时候，我总是觉得自己有一点想法，并试图实现（结果就是听取 WA 声一片），可以说浪费了很多时间（在这里卡了有一会儿了）。
当然，先行思考可以从失败中得到宝贵的教训；但即使没有先自己摸黑探索，学习经典算法的过程中也可以学到很多东西。我在尝试理解 Floyd-Warshall, Bellman-Ford 和 Dijkstra 三个算法的时候，也总结了不少经验。
我想，很多人在学习的过程中都陷入过死胡同，觉得自己的想法怎么也找不出问题。在这种状态中挣扎是很痛苦的，也是很无用的。我认为应该尽量避免进入这种状态；一旦进入，要尽快脱离出来。走进死胡同的原因，我个人认为一方面可能是过分依赖直觉，致使思维链条的某个环节出了错而不自知。我的解决办法是，把整个思维过程不断地梳理，尝试找出症结；另一方面则可能是基础不够牢靠，从而面对某个子问题时束手无策。我认为除了扎实积累以外别无他法。
说明
此博客只是我个人用作记录，并没有考虑易学性，可能不适合用作学习资料。
下面算法所用的图都是从 0 开始计结点数的。如果结点键不是数值，那么应该使用符号图（map 映射）。
这个算法的好处是实现起来非常简单，而且常数较小。它其实是多源最短路径算法，不过在这里一起学了。
Floyd-Warshall 算法基于动态规划。设 $d(k+1,i,j)$ 为「可以途径 0 ~ k 号结点，从 i 到 j 的最短路径长度」。
初始状态：每个点到自己的最短路径长度为 0。怎么表示呢？这一部分是我认为整个 Floyd-Warshall 算法里最聪明的一步，那就是约定 $k = -1$ 时表示「只使用 i 和 j 两个结点」，即
$$
d(0, i, j) = d(i + 1, i, j) = d(j + 1, i, j);
$$
前面之所以写成 $k + 1$ 而不是 $k$，是因为一般用数组记录的时候负的索引不太方便。
通过压缩和巧妙地利用边数组，可以把它写得很短：
for (Num k = 0; k < v_num; ++k)
for (Num i = 0; i < v_num; ++i)
for (Num j = 0; j < v_num; ++j)
if (d[i][j] < d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
基于「松弛」操作：对于起点 s，如果发现经由点 j 的邻接边到点 v 比目前的方法更短，那么就更新这条路径：
if (d[v] > d[j] + edge[j][v]) {
d[v] = d[j] + edge[j][v];
// and update the route.
}
Bellman-Ford 算法不断扫描所有的边，由于 d[s] 已经是最短的（0），所以每次扫描都一定可以延伸出去一部分。如果某次扫描没有更新任何路径，说明已经得到了最短路径，可以收手了。
如果存在负圈（路径和为负的圈），那么理论上这会成为一个死循环（只要在这个圈里走下去就可以更小）。因为对 v 个顶点而言最多只需要 v - 1 次循环（每次一定至少更新一个点），所以可以加入判断条件来判断是否有负圈。不过我没有加入这个操作。
这个算法做了非常多次无用的扫描，不一定是最好的算法。
我特意去查了他的名字怎么读。
如果没有负边，那么可以把所有点分成两部分：一部分是已经确定了最小路径的，我称为「圈内的」。因为没有负路径，所以不存在圈外的点，使得途径它的路径更短（绕远了）。
维护一个堆，所有新加入圈内的点能连到圈外的且确实能使路径变短的边都松弛一下并加入堆。这里不一定是最短路径，因为可能存在经由其它点的更短路径。相对的，堆里取出的也不一定是有效的最短路径，因为可能有别的点捷足先登了（这里这一份信息应该丢弃，因为它不是最短路径，它往后也不是最短路径）。
我写成了一坨，其实没有必要写成这样。
洛谷模板题：P3371
#include <iostream>
#include <queue>
#include <vector>
#define loop for (;;)
class Graph {
public:
using Num = unsigned;
using Weight_Type = unsigned;
constexpr static Weight_Type INF = (1u << 31) - 1;
// Actually I should be using `INF = std::numeric_limits<Weight_Type>::max() / 2 - 1`, but for
// specific use this may suffice.
Graph(Num vertex_num)
: v_num(vertex_num), adj_list(std::vector<std::vector<Edge>>(vertex_num)),
adj_matrix(std::vector<std::vector<Weight_Type>>(
vertex_num, std::vector<Weight_Type>(vertex_num, INF))) {}
void add_edge(Num from, Num to, Weight_Type weight) {
edges.push_back({from, to, weight});
adj_list[from].push_back({from, to, weight});
adj_matrix[from][to] = adj_matrix[to][from] = weight;
}
std::vector<Weight_Type> sp_Bellman_Ford(Num start) const {
std::vector<Weight_Type> ret(v_num, INF);
ret[start] = 0;
loop {
bool update = false;
for (auto const &edge : edges)
if (ret[edge.from] != INF && ret[edge.to] > ret[edge.from] + edge.weight) {
ret[edge.to] = ret[edge.from] + edge.weight;
update = true;
}
if (update == false)
break;
}
return ret;
}
std::vector<Weight_Type> sp_Dijkstra(Num start) const {
std::vector<Weight_Type> ret(v_num, INF);
ret[start] = 0;
struct Record {
Weight_Type crnt_sp;
Num to;
bool operator>(Record const &a) const { return crnt_sp > a.crnt_sp; }
};
std::priority_queue<Record, std::vector<Record>, std::greater<Record>> pq;
pq.push({0, start});
while (pq.empty() == false) {
auto rec = pq.top();
pq.pop();
if (rec.crnt_sp > ret[rec.to])
continue; // Other vertices have already relaxed this one.
for (auto i : adj_list[rec.to]) {
if (ret[i.to] > ret[i.from] + i.weight) {
ret[i.to] = ret[i.from] + i.weight;
pq.push({ret[i.to], i.to});
}
}
}
return ret;
}
std::vector<Weight_Type> sp_Floyd_Warshall(Num start) const {
auto d = adj_matrix;
for (Num k = 0; k < v_num; ++k)
for (Num i = 0; i < v_num; ++i)
for (Num j = 0; j < v_num; ++j)
if (d[i][j] < d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
return d[start];
}
private:
struct Edge {
Num from;
Num to;
Weight_Type weight;
};
Num v_num;
std::vector<Edge> edges;
std::vector<std::vector<Edge>> adj_list; // Adjacent List;
std::vector<std::vector<Weight_Type>> adj_matrix; // Adjacent Matrix;
/*
共实如果只用 Bellman-ford 求最短路，不需要下面那个邻接表；如果只用 Dijkstra 反之。
我把它们放在了一块而已。
如果使用的是 Floyd-Warshall 算法，一番好用的是邻接矩阵。在这里我也加上了。233，三
个算法顺手的表示方法都不同。
说实话，我的代码有点过度复杂了。其实核心代码就那么不几句而已。这个做法在 OI 等竞赛中
应该是不被提倡的。
*/
};
int main() {
using std::cin;
using std::cout;
unsigned n, m, s;
cin >> n >> m >> s;
Graph g(n);
for (unsigned i = 0; i < m; ++i) {
unsigned u, v, w;
cin >> u >> v >> w;
g.add_edge(u - 1, v - 1, w);
}
auto sp = g.sp_Bellman_Ford(s - 1); // Or else.
for (auto const i : sp)
cout << i << ' ';
cout << '\n';
}
Thanks for reading~