图论——最短路径问题（bellman-ford、dijkstra、Floyd）_综合

前言

在一张图中，我们需要寻找到两个点之间的最短路径，这个问题在实际中也是很常用的。
最短路径问题分为单源最短路径和任意两点之间的最短路径问题。

单源最短路径

输入一个有向加权图，我们要返回这个顶点到剩余顶点的最小距离。
注意权值非负，如果有负圈，那么一些最短路径将会不存在。（一直在那里绕，路径为无穷小）

优化子结构

没错，这个问题涉及到了dp和贪心的解法，我们接下来进行讲解。

最短路径的子路径也一定是最短。
这个我们就可以通过反证法来证明，如果最短路径的子路经不是最短，那么我们直接替换就能将当前的最短路径优化。

松弛

这个是最短路径的核心部分，在图部分我们到达一个顶点的方式有很多，可能是直接到达，也可能中间绕路，松弛的本质就是比较绕路和直接到达的代价，从而得到最优解。
（绕路也不一定会远，这要看我们的权值是怎么样的。）

bellman-ford算法

BellmanFord()
//初始化
for each v ∈ Vd[v] = ∞;
d[s] = 0;
//松弛
for i=1 to |V|-1for each edge (u,v) ∈ ERelax(u,v, w(u,v));
//检测是否还有能松弛的
for each edge (u,v) ∈ Eif (d[v] > d[u] + w(u,v))return “no solution”;

这个算法还是比较正经的。

开始因为要找最短距离，所以需要进行初始化，然后第一个结点到第一个结点置为0。
然后就需要进行松弛，这里我们的 i 只是一个计数器。
最后是一个检测，如果还有能松弛的，就是有负圈了，这样的就没有最短路径了。

很明显的一个个尝试，所以这个算法就是属于dp问题的，我们每一次循环将所有的边松弛一次，最终得到正确结果。这里说明一下，我们的边集顺序会影响到我们最终得到最终结果的速度的。

运行时间：O(VE)，V为顶点集，E为边集。因为我们是外层的计数器为V，内层将每一个边操作一次。

证明
我们的V-1次循环收缩边，每一次都相当于有一个顶点确定下来，现在我们证明一下我们的算法是正确的。
我们考虑其中的一个顶点v，有这样的路径s->v1->v2->……->v。
因为我们的优化子结构，所以当我们得到v的最优解的时候，很明显前面的所有点都已经是最优的了。
同样，我们如果有了前面的最优解，那么我们就能一定能得到下一个点的最优解。

（有一点乱，不过想起来还是比较舒服的，不太会写）

dijkstra

我们有没有更好的办法，而不是这样的一次次来尝试。
如果说bellman-Ford是不断的松弛，最终找到答案，那么dijkstra算法就是直接判断出哪一个就是最优解，直接选择不需要判断。这也说明该算法其实属于一种贪心算法。

前提：图中没有负边

Dijkstra(G)
//初始化
for each v ∈ Vd[v] = ∞;
d[s] = 0; 
Q = V;
//松弛
while (Q)							//表示Q非空u = ExtractMin(Q);				//选出for each v ∈ u->Adj[]if (d[v] > d[u]+w(u,v))d[v] = d[u]+w(u,v);

最开始的初始化和bellman差不多，不说了
我们这次使用的是堆Q，最开始为顶点全集，为我们没有遍历的点的集合（当然了，第一次取出起点s）
每一次从没遍历的顶点中取出最近的（堆比较的是d[v]），将其划入已经遍历的顶点集，也就是拿出来
然后我们就需要将这个顶点相邻的所有顶点进行松弛。
（这里松弛部分也简化了很多，不是每一次都需要松弛所有边了）

之前说过，dijkstra是贪心算法，那么我们就需要进行证明。
优化子结构问题不用说了，这几个算法都有，看上面。
贪心选择性：
我们假设已经遍历的为S0，还没遍历的为S1，此时有一个y∈S1，是S1中距离S0最近的。
dijkstra算法将拿出这个顶点y，也就是说明此时我们一定能得到y顶点的最短距离。
我们假设如果还有一条路径，从s到y更近，那么就一定是要从另外一个点绕一下的（直接的我们已经有了）我们假设这个点是x。
在这里插入图片描述
但是我们已经知道了，S0到y的距离小于到x的距离，x再加上到y的距离是一定要大于直接到y的距离的，所以我们可以判定我们的y此时一定是最优解。

任意两点之间的最短路径

问题：找到图中每一对结点间最短路径
这里仍为有向加权图，保证没有负圈（但可能有负边）

既然是任意两点，那么我们就调用V次的bellman么。（dijkstra因为有负边不能用）

这好吗，这不好。

接下来我们给出Floyd算法：

给出一个公常识：可以将有向图（包括无向图）的权值写在矩阵中；
我们的从a到b可能是直接到达，也可能是经过了好几个点，我们需要进行松弛，找到最优解作为返回值；
接下来我们定义子问题，这个子问题和之前的不太一样：我们将一部分点形成的任意两点间最短路径作为子问题。
联系2&3，我们的解法就得到了：对于ab这一组点，最开始只有这两个点，我们不断扩大点集，通过绕路的方式不断修改ab间最短路径（其实就是在松弛），最终当所有点都在图上，我们就能得到最短路径。
假设一共有n个点，我们设每一个最短距离为D^o[a][b]，……Dⁿ[a][b]
如何通过D^n-1[a][b]计算Dⁿ[a][b]？按照定义我们需要比较D^n-1[a][b]和D^n-1[a][k]+D^n-1[k][b]。
我们已经证明了松弛一定能得到当前最优解，因为是不断增加点，而最开始的D^o就是我们输入的权矩阵，那个要不是最简直接爬行吧。因此我们可以得出结论，经过上述过程，我们就能得到a到b的最短路径。
同理，我们将每一对点都这样做（直接放在矩阵中），就可以得到正确答案了。

给出算法伪代码：

Floyd(W)
D^0 = W		//初始化`在这里插入代码片`
P = {0}		//代表0矩阵
for k = 1 to n							//每一次加点for i = 1 to n						//双重循环每一对顶点for j = 1 to nif (D^k-1 [i][j] > D^k-1 [i][k] + D^k-1 [k][j] )D^k [i][j] = D^k-1 [i][k] + D^k-1 [k][j]//P[i][j] = kelse D^k[i][j] = D^k-1 [i][j]

这里有一行加了注释，是我们用来存储经过的点的矩阵。
这里我们采用滚动数组的思想，只需要两个矩阵相互交叉覆盖就能实现功能；
在学习的过程中，我还看到可以直接在原矩阵上进行覆盖，这个不知道会不会影响，所以就没有给出。

这里给出一个自己不算很严谨的思考：我们假设用[i][k]+[k][j]覆盖了[i][j]，在我们求[i][k]时，我们也不会再使用到j，因为[i][j]就已经比[i][k]大了，所以覆盖掉问题应该不大。

最后补一个打印路径的递归函数：

path(P,q,r)
if (P[q,r] != 0) path(q, P[q,r])println(“v” + P[q,r])  //实现打印vi（矩阵中的值为下标），表示顶点path(P[q,r], r)return;
else return