各种最短路的模板！
首先可以利用反证法证明一个定理：
最短路径的子路径也是最短路径。
这个定理构成了之后算法的基石。
同时还有一个重要的不等式：
这个不等式叫三角不等式，它是松弛操作的理论基础。
Bellman-Ford 算法
容易知道，当一个图 $G=(V, E)$ 中不存在负环时，该图中的最短路最多经过 $|V|-1$ 条边。最短路上是不可能存在一个路径的权重和为正的环的。因此进行松弛操作时，最多进行 $|V|-1$ 次就可以算出最短路。若在第 $|V|$ 次仍可以进行松弛，那么就说明存在一个负环。
Bellman-Ford 算法基于上述思路，对每一条边都进行 $|V|-1$ 次的松弛，从而就可求出最短路。同时，也可以用于判断负环是否存在。
从上述说明也可以看出，Bellman-Ford 算法允许图中有负权边。1
2
3
4
5
6
7
8
9
10
11
12
13
14bool Bellman_Ford(){
for(int i = 1; i < V; ++i)
for(int j = 0; j < E; ++j){
int u = edge[j].from, v = edge[j].to;
if(d[v] > d[u] + edge[j].cost)
d[v] = d[u] + edge[j].cost;
}
for(int j = 0; j < E; ++j){
int u = edge[j].from, v = edge[j].to;
if(d[v] > d[u] + edge[j].cost)
return false;//还能松弛说明这个图存在负环
}
return true;
}
除了上述写法，还有一种经过了一定优化的写法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16bool Bellman_Ford(){
for(int i = 1; i <= V; ++i){
int flag = 0;
for(int j = 0; j < E; ++j){
int u = edge[j].from, v = edge[j].to;
if(d[v] > d[u] + edge[j].cost){
d[v] = d[u] + edge[j].cost, flag = 1;
if(i == V)
return false;
}
}
if(!flag)
break;//松弛的次数已经足够了，没有必要再进行下去
}
return true;
}
容易看出，Bellman-Ford 算法的时间复杂度为 $O(|V|\times |E|)$。因此，大部分情况下 Bellman-Ford 算法在解决问题的时候时间复杂度都不够好。但是，它的一个优化版本——SPFA 的应用场合就相当多了。
SPFA 算法
SPFA 算法其实应该叫做队列优化了的 Bellman-Ford 算法，SPFA 只是国内的一种叫法。
它的实现基于队列：先将源点放入队列，然后重复以下过程：从队列中取出点，尝试对和它相邻的所有点进行松弛操作，若对其邻居 $v$ 松弛成功并且 $v$ 不在队列中则将 $v$ 放入队列。队列为空则表明没有可以再松弛的边。
和在 Bellman-Ford 算法中的分析类似，如果一个点进入队列达到 $|V|$ 次，就表明存在负环。
SPFA 算法在稀疏图上表现效果很好，但是在经过构造的数据下表现和 Bellman-Ford 算法基本相同。因此，SPFA 算法的使用有一定的危险性。
1 |
Dijkstra 算法
DIjkstra 算法在求单源最短路方面表现相当稳定。朴素实现时它的时间复杂度为 $O(|V|^2+|E|)$，而在使用一定的数据结构时可以将时间复杂度降到 $O(|E|log|V|)$。
Dijkstra算法的使用条件是图中没有负权边。当图中的边权全为正时，可以从起点出发，采用贪心的方法，一步一步得到最短路径。
具体方法是：找出所有没有使用过的顶点中离起点最近的点，然后松弛所有与其相邻的边，将其加入已使用过的点的集合，重复这一步骤。这样可以保证：每一次点在被使用时，之前算出来的起点到它的“最短距离”就是实际的起点到它的最短距离。这可以用归纳法证明。
朴素版本如下：1
2
3
4
5
6
7
8
9
10
11
12
13void dijkstra(int S){
memset(d, 0x3f, sizeof(d));
d[S] = 0;
for(int i = 0; i < V; ++i){
int mind = 2000000000, minp = -1;
for(int j = 0; j < V; ++j)
if(mind > d[j] && !vis[j])
mind = d[j], minp = j;//寻找当前扩展点
vis[minp] = true;
for(int j = at[minp]; j; j = e[j].nxt)
d[e[j].v] = min(d[e[j].v], d[minp] + e[j].cost);//松弛
}
}
用堆优化的版本如下：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
30struct Node{
int id, curd;
Node(int _id, int _curd){
id = _id, curd = _curd;
}
};
struct cmp{
inline bool operator() (const Node &na, const Node &nb){
return na.curd > nb.curd;
}
};
priority_queue<Node, vector<Node>, cmp> pq;
void dijkstra(int S){
memset(d, 0x3f, sizeof(d));
d[S] = 0;
pq.push(Node(S, 0));
for(int i = 0; i < V; ++i){
while(!pq.empty()){
if(pq.top().curd > d[pq.top().id])//用这种方式省去了一个vis数组
pq.pop();
else break;
}
int minp = pq.top().id;
pq.pop();
for(int i = at[minp]; i; i = e[i].nxt){
if(d[e[i].v] > d[minp] + e[i].cost)
d[e[i].v] = d[minp] + e[i].cost, pq.push(Node(e[i].v, d[e[i].v]));//通过这种方式判断是否已被访问
}
}
}
朴素搜索
当边权相同或者图很特殊（如$DAG$）时，可以直接采用搜索或者递推的方式计算最短路。由于这不是一个统一的模型，故在此不给出代码。
以上算法一般用于解决单源最短路问题。
矩阵乘法
将图上的边距离对应成矩阵中相应行列的一个点，即可构造出一个矩阵
Floyd算法
Floyd最短路算法可以在$O(|V|^3)$的时间复杂度下解决多源最短路问题。
Floyd算法用到了动态规划的思想。考虑原始情况下，令$d[i][j]$表示点$i$和点$j$之间的最短距离。但这并不够用来表示一个状态，因此我们加上一维$k$，令$d[k][i][j]$表示利用编号为$0$到$k - 1$的点作为中转站时，$i$和$j$之间的最短距离。初始化时令$d[0][i][j] = cost[i][j]$（此时认为不使用中转站），其他值设为$INF$。
在$0$到$k-1$的答案被算出来后，考虑$k$的情况。当不以$k$为中转站时，有$d[k+1][i][j]=d[k][i][j]$；当以$k$为中转站时，有$d[k+1][i][j]=d[k][i][k]+d[k][k][j]$。结合一下就是
可以发现，此时第一维已经没有什么必要。故最后我们可以得到以下代码。1
2
3
4
5
6
7void Floyd(){
//此时d数组里面已经存了相关信息
for(int k = 0; k < V; ++k)
for(int i = 0; i < V; ++i)
for(int j = 0; j < V; ++j)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
Floyd算法允许负权边的存在，同时也可以用来判断负环是否存在。当负环存在时，存在$i$使得$d[i][i]<0$。
Floyd算法在一些和动态规划有所联系的图论题目里也有不错的表现，比如题目最小密度路径里面，可以增加一维记录当前走过的路径的条数，然后求出恰好经过一定数目路径的最短路的长度。
同时Floyd算法的实现性也很强，很容易实现。不过似乎Floyd算法无法求出最短路径树。
参考资料
- 《算法导论》
- 《挑战程序设计竞赛（第2版）》
- 相关博客