文章目录
  1. 1. 单源最短路
    1. 1.1. 迪杰斯特拉(Dijkstra)算法
    2. 1.2. 贝尔曼福特(BelLnam-Ford)算法
  2. 2. 多源最短路
    1. 2.1. 弗洛伊德(Floyd-Warshall)算法

引言: 数据结构学到最短路径了,总结一下几个算法。


单源最短路

迪杰斯特拉(Dijkstra)算法

迪杰斯特拉算法有点像之前学的用来求最小生成树的Prim(普里姆)算法,我认为迪杰斯特拉也是贪心算法的一种。

题设:假设有点0~6,求点0到其他各点的最短路径长度。

我用“最短路”表示已求得的最终最短路径,用“最短路径长度”表示目前到达该点所需经过的最短路径,则迪杰斯特拉的思路是:

  1. 我们建一个辅助数组,存放目前0到各个点的最短路径长度
  2. 先找到0到1~6中最短的直连边,这就是最短路,而且是最短路中的最短的那条(最终结果求得0到1~6的各个最短路中它是最短的那个,第二次重复该步骤得到次短最短路,以此类推)

解释:假设0到4的边是0到1~6中最短的直连边,该直连边就是0到4的最短路。用反证法:

若存在0到4的路径中至少经过1个点n(n∈[1,6]),由于l0l\geqslant0 ,那么0到4的路径长度 l04l0n+ln4l_{04}\geqslant l_{0n}+l_{n4} ,由已知l04l_{04}是各直连边中的最短直连边,即l04l0nl_{04}\leqslant l_{0n} ,与前一个不等式推出矛盾。

  1. 假设步骤2找到l04l_{04}为最短路,则现在将0和4视为一个点0(姑且称为缩点),如果l0n>l04+l4nl_{0n}\gt l_{04}+l_{4n},则用l04+l4nl_{04}+l_{4n} 的值替换掉辅助数组中点n目前所存放的最短路径长度,即更新点4关联点的最短路径长度。
  2. 重复步骤2和3,直到将所有点缩成1个点,完成算法

可以看到,这个算法成立的条件必须是图中没有负边。

贝尔曼福特(BelLnam-Ford)算法

相比前面的迪杰斯特拉算法,贝尔曼福特一个DP算法,我认为DP算法和数学归纳法有点相似。

题设:假设有点0~n-1一共n个点,求点0到其他各点的最短路径长度。

我仍然用“最短路”表示已求得的最终最短路径,用“最短路径长度”表示目前到达该点所需经过的最短路径,算法思路:

  1. 提出这样一个前提:在没有路径长度为负值的回路的n点图中,任意两点若存在最短路,则两点间最多经过n-1条边。

解释:(建议先看完算法思路再看解释)n点图中加入n-1条边后成为连通图,则必定不存在回路。任意增加一条边则必定形成回路 或 使得新边成为相连两点的第二条通路。

情况1: 形成回路。按照算法步骤和思路,则说明0到1经过abcd的路径长度小于经过a的路径长度,意为b+c+d<0,与“不存在路径长度为负值的回路”所矛盾。

情况2: 新边成为相连两点的第二条通路。按照算法步骤和思路,若已存在0到2经过2条边的通路ab,则意为ab长度(weight)小于任意0到2的经过1条边的通路,即a+b<c,即c不应加入并且它的加入是无意义的。

  1. 我们继续……考虑这样一种情况,我的辅助数组已经分别存放了在最多加入k条边之后,从点0到达点m(m∈[1,n-1])的最短路径长度(注意,从0到达点1~n-1所加入的k条边不一定一样)

  2. 现在要求得最多经过k+1条边之后,从点0到达点m(m∈[1,n-1])的最短路径长度。记为L0mk+1(m[1,n1])L_{0m}^{k+1} (m\in [1,n-1]),显然有:

L0mk+1=min{L01k+l1m,L02k+l2m,L03k+l3m,...,L0(n1)k+l(n1)m}L_{0m}^{k+1}=\min\{L_{01}^k+l_{1m},L_{02}^k+l_{2m},L_{03}^k+l_{3m},...,L_{0(n-1)}^k+l_{(n-1)m}\}

即从任意的k条边的通路的终点直接连过来看看哪个最小,再跟已经求得的最短路径长度(最多包含k条边)进行比较,取小的作为最多包含k+1条边的最短路径长度。

  1. 算法以最多经过n-1条边为结束。

上述步骤3是求得一个点的k+1最短路径长度,求这个点的时候遍历所有通路终点,也就是说要完成求一轮的过程需要O(n2)O(n^2)的复杂度,考虑要进行n-1轮(加入n-1条边),那就是O(n3)O(n^3)的复杂度,这太高了,因为有的labl_{ab}是不存在的,不需要参与比较。

上述做法是遍历点,经过优化我们采用遍历边来规避这个缺点。

具体算法实施是O(VE)O(VE)O(nE)O(nE)的(由于EE最多为n2n^2数量级,所以复杂度最差才为O(n3)O(n^3),可以看出适用于稀疏图)。具体做法是遍历以1~n-1每个顶点为起点的边进行松弛来实现的,对每一个m∈[1,n-1],记过程中数组存放点0到点m最多包含k+1条边的短路径长度为L[m](其实是滚动了),考虑对边l[j]l_{[j]}进行遍历:

L[l[j].destination]=min{L[l[j].destination],L[l[j].origin]+l[j].value}L[l_{[j]}.destination]=\min\{L[l_{[j]}.destination], L[l_{[j]}.origin]+l_{[j]}.value\}

假设我们正在从经过最多k条边更新到经过最多k+1条边,有人会担心这样写会不会刚用更新过的L[l[j].origin]L[l_{[j]}.origin] (已经被更新为经过最多k+1条边了)去更新L[l[j]destination]L[l_{[j]}destination] (还未更新过),这样的滚动不就是失败且混乱的了吗?

解释:如果用刚更新过的L[l[j].origin]L[l_{[j]}.origin]去更新L[l[j].destination]L[l_{[j]}.destination] ,就相当对L[l[j].destination]L[l_{[j]}.destination]进行个别的第k+2轮更新,这次的个别更新会在下一轮中重复一次。

又有人担心应该用更新前的L[l[j].origin]L[l_{[j]}.origin]去更新L[l[j].destination]L[l_{[j]}.destination] ,其实没必要,首先说明如果L[l[j].origin]L[l_{[j]}.origin]被更新过,说明现在的L[l[j].origin]L[l_{[j]}.origin]值比更新前的经过最多k条边的值还要小。按照上条解释,L[l[j].destination]L[l_{[j]}.destination]会被相同的做法在k+2轮更新一次,由于它更小,那么在k+2轮中,也会被更新到这个状态来。

以下是Bellman-Ford代码【查看援引文章】:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
* About: Bellman-Ford算法
* Author: Tanky Woo
* Blog: www.WuTianqi.com
*/

#include <iostream>
using namespace std;
const int maxnum = 100;
const int maxint = 99999;

// 边,
typedef struct Edge{
int u, v; // 起点,重点
int weight; // 边的权值
}Edge;

Edge edge[maxnum]; // 保存边的值
int dist[maxnum]; // 结点到源点最小距离

int nodenum, edgenum, source; // 结点数,边数,源点

// 初始化图
void init()
{
// 输入结点数,边数,源点
cin >> nodenum >> edgenum >> source;
for(int i=1; i<=nodenum; ++i)
dist[i] = maxint;
dist[source] = 0;
for(int i=1; i<=edgenum; ++i)
{
cin >> edge[i].u >> edge[i].v >> edge[i].weight;
if(edge[i].u == source) //注意这里设置初始情况
dist[edge[i].v] = edge[i].weight;
}
}

// 松弛计算
void relax(int u, int v, int weight)
{
if(dist[v] > dist[u] + weight)
dist[v] = dist[u] + weight;
}

bool Bellman_Ford()
{
for(int i=1; i<=nodenum-1; ++i)
for(int j=1; j<=edgenum; ++j)
relax(edge[j].u, edge[j].v, edge[j].weight);
bool flag = 1;
// 判断是否有负环路
for(int i=1; i<=edgenum; ++i)
if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)
{
flag = 0;
break;
}
return flag;
}
int main()
{
//freopen("input3.txt", "r", stdin);
init();
if(Bellman_Ford())
for(int i = 1 ;i <= nodenum; i++)
cout << dist[i] << endl;
return 0;
}

推荐阅读:【贝尔曼福特算法优化】

多源最短路

弗洛伊德(Floyd-Warshall)算法

comments powered by HyperComments
文章目录
  1. 1. 单源最短路
    1. 1.1. 迪杰斯特拉(Dijkstra)算法
    2. 1.2. 贝尔曼福特(BelLnam-Ford)算法
  2. 2. 多源最短路
    1. 2.1. 弗洛伊德(Floyd-Warshall)算法