[图论]最短路三大算法——Dijkstra算法,Bellman-ford,floyed

Dijkstra算法(单源最短路径)

步骤

  1. 初使时令 S={V0},T={其余顶点},T中顶点对应的距离值, 若存在<V0,Vi>,为<V0,Vi>弧上的权值(和SPFA初始化方式不同),若不存在<V0,Vi>,为Inf。
  2. 从T中选取一个其距离值为最小的顶点W(贪心体现在此处),加入S(注意不是直接从S集合中选取,理解这个对于理解vis数组的作用至关重要),对T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值比不加W的路径要短,则修改此距离值(上面两个并列for循环,使用最小点更新)。
  3. 重复上述步骤,直到S中包含所有顶点,即S=V为止(说明最外层是除起点外的遍历)。
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
const int INF=0x3f3f3f3f;
const int maxn=1200;

int dist[maxn],g[maxn][maxn],N;
bool vis[maxn];

void dijkstra()
{
for(int i=1;i<=N;i++)
dist[i]=(i==1)?0:INF;
memset(vis,0,sizeof(vis));

for(int i=1;i<=N;i++)
{
int mark=-1,mindis=INF;
for(int j=1;j<=N;j++)
{
if(!vis[j]&&dist[j]<mindis)
{
mindis=dist[j];
mark=j;
}
}
vis[mark]=1;

for(int j=1;j<=N;j++)
{
if(!vis[j])
{
dist[j]=min(dist[j],dist[mark]+g[mark][j]);
}
}
}
}

Bellman-ford(单元最短路径,可带负环)

为了能够求解边上带有负值的单源最短路径问题,Bellman(贝尔曼,动态规划提出者)和Ford(福特)提出了从源点逐次绕过其他顶点,以缩短到达终点的最短路径长度的方法。Bellman-ford算法是求含负权图的单源最短路径算法,效率很低,但代码很容易写。即进行不停地松弛,每次松弛把每条边都更新一下,若n-1次松弛后还能更新,则说明图中有负环,无法得出结果,否则就成功完成。Bellman-ford算法有一个小优化:每次松弛先设一个flag,初值为FALSE,若有边更新则赋值为TRUE,最终如果还是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间做无必要的松弛,所以SPFA算法用队列进行了优化,效果十分显著,高效难以想象。SPFA还有SLF,LLL,滚动数组等优化。

递推公式(求顶点u到源点v的最短路径):
$$
dist 1 [u] = Edge[v][u]
$$

$$
dist k [u] = min{ dist k-1 [u], min{ dist k-1 [j] + Edge[j][u] } }, j=0,1,…,n-1,j≠u
$$

Dijkstra算法和Bellman算法思想有很大的区别:Dijkstra算法在求解过程中,源点到集合S内各顶点的最短路径一旦求出,则之后不变了,修改 的仅仅是源点到T集合中各顶点的最短路径长度。Bellman算法在求解过程中,每次循环都要修改所有顶点的dist[ ],也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来。

使用条件

  • 单源最短路径(从源点s到其它所有顶点v)
  • 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)
  • 边权可正可负(如有负权回路输出错误提示)
  • 差分约束系统(至今貌似只看过一道题)

描述

  1. 初始化:将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0
  2. 迭代求解:反复对边集E中的每条边进行松弛操作,使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离;(运行|v|-1次,看下面的描述性证明(当做树))
  3. 检验负权回路:判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点,则算法返回false,表明问题无解;否则算法返回true,并且从源点可达的顶点v的最短距离保存在d[v]中

Bellman-Ford算法是否一定要循环n-1次么?未必!其实只要在某次循环过程中,考虑每条边后,都没能改变当前源点到所有顶点的最短路径长度,那么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
bool Bellman_Ford()

{

for(int i = 1; i <= nodenum; ++i) //初始化

dis[i] = (i == original ? 0 : MAX);

for(int i = 1; i <= nodenum - 1; ++i)

for(int j = 1; j <= edgenum; ++j)

if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛(顺序一定不能反~)

{

dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;

pre[edge[j].v] = edge[j].u;

}

bool flag = 1; //判断是否含有负权回路

for(int i = 1; i <= edgenum; ++i)

if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)

{

flag = 0;

break;

}

return flag;

}

SPFA

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
#include<bits/stdc++.h>
#define N 105
int res[N];//存储源点到每个顶点的最短距离值
int g[N][N];
int cnt[N];//每个点入队次数,判断是否出现负环
int que[N*N];//队列
bool in_que[N];//标记一个点是否已在队列中
int front;//队首位置
int rear;//队尾位置
void spfa(int n,int src)
{
rear=front=0;
que[++rear]=src;
memset(res,0x3f3f3f3f,sizeof(res));
memset(in_que,0,sizeof(in_que));
res[src]=0;
while(front<rear)
{
int cur=que[++front];
in_que[cur]=0;
int i;
for(i=1; i<=n; i++)
{
if(res[cur]+g[cur][i]<res[i])
{
res[i]=res[cur]+g[cur][i];
if(!in_que[i])
{
que[++rear]=i;
in_que=1;
}
}
}
}
}

floyed(全源最短路径)

Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎2种可能,1是直接从A到B,2是从A经过若干个节点到B,所以,我们假设dist(AB)为节点A到节点B的最短路径的距离,对于每一个节点K,我们检查dist(AK) + dist(KB) < dist(AB)是否成立,如果成立,证明从A到K再到B的路径比A直接到B的路径短,我们便设置 dist(AB) = dist(AK) + dist(KB),这样一来,当我们遍历完所有节点K,dist(AB)中记录的便是A到B的最短路径的距离。

1
2
3
4
5
6
7
8
9
for (int k=0; k<n; ++k)
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
/*
实际中为防止溢出,往往需要选判断 dist[i][k]和dist[k][j]
都不是Inf ,只要一个是Inf,那么就肯定不必更新。
*/
if (dist[i][k] + dist[k][j] < dist[i][j] )
dist[i][j] = dist[i][k] + dist[k][j];

Floyd算法另一种理解DP,为理论爱好者准备的,上面这个形式的算法其实是Floyd算法的精简版,而真正的Floyd算法是一种基于DP(Dynamic Programming)的最短路径算法。设图G中n 个顶点的编号为1到n。令c [i, j, k]表示从i 到j 的最短路径的长度,其中k 表示该路径中的最大顶点,也就是说c[i,j,k]这条最短路径所通过的中间顶点最大不超过k。因此,如果G中包含边<i, j>,则c[i, j, 0] =边<i, j> 的长度;若i= j ,则c[i,j,0]=0;如果G中不包含边<i, j>,则c (i, j, 0)= +∞。c[i, j, n] 则是从i 到j 的最短路径的长度。对于任意的k>0,通过分析可以得到:中间顶点不超过k 的i 到j 的最短路径有两种可能:该路径含或不含中间顶点k。若不含,则该路径长度应为c[i, j, k-1],否则长度为 c[i, k, k-1] +c [k, j, k-1]。c[i, j, k]可取两者中的最小值。状态转移方程:c[i, j, k]=min{c[i, j, k-1], c [i, k, k-1]+c [k, j, k-1]},k>0。这样,问题便具有了最优子结构性质,可以用动态规划方法来求解。


纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!