【算法导论学习笔记】 单源最短路径 Dijkstra算法 Bellman-Ford算法 SPFA算法_以下哪种算法可以解决存在负权边的单源最短路问题

单源最短路径

给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径问题。

Dijkstra算法
Bellman-Ford算法
SPFA算法（Bellman-Ford的队列优化）

Dijkstra算法

迪杰斯特拉(Dijkstra)算法，每一步示例：
https://blog.csdn.net/xiaoxi_hahaha/article/details/110257368
Dijkstra算法及其堆优化代码详解：
https://blog.csdn.net/Selenitic_G/article/details/89657943

算法简介：
迪杰斯特拉算法是由荷兰计算机科学家在1956年发现的算法，此算法使用类似广度优先搜索的方法解决了带权图的单源最短路径问题。它是一个贪心算法。

算法思路：
迪杰斯特拉算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值，其在运行过程中维持的关键信息是一组节点集合S。算法重复从结点集V-S中选择最短路径估计最小的结点u，将u加入到集合S，然后对所有从u发生的边进行松弛，运行结束后，从源节点到集合S中每个结点之间的最短路径已经被找到。

以下代码用c++代码实现了Dijkstra，时间复杂度为O(v^2);
但是如果使用堆优化的Dijkstra算法，可以达成O(elogv)的时间复杂度;

#include <iostream>
using namespace std;
/*问题描述：
 * 输入n和m，代表n个节点，m条边，然后是m行输入，每行有x,y,z，代表x到y的路距离为z。
 * 问题：从1出发到各点的最短路径。
 * 测试样例：
7 12
1 2 20
1 3 50
1 4 30
2 3 25
2 6 70
3 4 40
3 6 50
3 5 25
4 5 55
5 6 10
5 7 70
6 7 50
 */
const int maxn = 100;
int map[maxn][maxn]; // 有邻接矩阵的方式存储图
int dis[maxn];       // 存储到每个点的最短距离
int vis[maxn];       // 记录是否是已经到达的点
int path[maxn];      // 以前驱的形式记录最短路径
int n;
void Dijkstra(int s) // i表示起始节点
{
    // 初始化，最初到底距离都是无限大，每一个点都不是已到达顶点。
    for (int i = 0; i <= n; i++)
    {
        dis[i] = 0x3f3f3f3f;
        vis[i] = 0;
        path[i] = -1;
    }
    // 一开始到i的距离是0，只有i是已经到达顶点
    dis[s] = 0;
    while (true)
    {
        int k = 0;
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && dis[i] < dis[k]) // 未收录顶点中，最短的那个。第一次是s。
                k = i;
        }
        if (k == 0)
            return;
        vis[k] = 1;
        for (int i = 1; i <= n; i++)
        {
            if (dis[i] > dis[k] + map[k][i])
            {
                dis[i] = dis[k] + map[k][i];
                path[i] = k;
            }
        }
    }
}

void getPath(int order)
{
    if (path[order] == -1)
        return;
    getPath(path[order]);
    cout << "->" << order;
}

int main()
{
    int m, x, y, z, order;
    cin >> n >> m;
    for (int i = 0; i < maxn; i++)
        for (int j = 0; j < maxn; j++)
            map[i][j] = 0x3f3f3f3f;
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y >> z;
        map[x][y] = z;
    }
    Dijkstra(1);
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    return 0;
}
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

Bellman-Ford算法

参考文章：
https://blog.csdn.net/qq_52905520/article/details/126453516
https://blog.csdn.net/m0_58151858/article/details/124204854

什么是Bellman-ford算法

贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼（Richard Bellman）和莱斯特·福特创立的，求解单源最短路径问题的一种算法。其优于Dijkstra的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高。但它也有特别的用处，一般用于实现通过m次迭代求出从起点到终点不超过m条边构成的最短路径。

Dijkstra算法不能解决带有负权边的问题，而Bellman-ford算法可以解决带有负权边的问题，是求解带负权边的单源最短路问题的经典算法。时间复杂度是O(nm)，核心思想是”松弛操作”。解决带负权边的单源最短路问题还有一个常用的算法是SPFA算法，SPFA算法的时间复杂度一般是O(m)，最坏是O(nm)。

总结一下就是Dijkstra算法可以解决不带负权边的问题，而对于带有负权边的问题，又有Bellman-ford算法和SPFA解决。

基本思路

首先n次迭代，每一次循环所有边。我们这里用a,b,w表示存在一条从a走到b的边，权重是w。这里存边方式有很多种，可以用邻接表，结构体等。遍历所有边的时候更新一下其他点的距离，和Dijkstra算法类似，用当前这个点更新和它相连的点距离起点的距离。我们这里用dist数组表示每个点到起点的距离，那么更新操作就是dist[b]=min(dist[b],dist[a]+w)，这样就可以更新和a相连的b点距离起点的距离，这个更新的过程就是”松弛操作”。忘了说的一点就是在循环所有边的时候，每一次循环要先把dist数组备份一下，防止串联，这个后面会说。循环n次之后对所有的边一定满足dist[b]<=dist[a]+w，这个叫”三角不等式”。

这个就是Bellman-ford算法的基本思路。

但是注意如果图中有负权回路的话，最短路就不一定存在了

下面是c++代码实现：

#include <iostream>
using namespace std;

const int N = 101, M = 101;

int n, m;
int dis[N];

struct node
{
    int a, b, w;
} edge[M];

void BellmanFord(int s)
{
    for (int i = 1; i <= n; i++)
        dis[i] = 0x3f3f3f3f;
    dis[s] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int a = edge[j].a, b = edge[j].b, w = edge[j].w;
            if (dis[b] > dis[a] + w)
                dis[b] = dis[a] + w;
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        edge[i].a = a;
        edge[i].b = b;
        edge[i].w = w;
    }
    BellmanFord(1);
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    return 0;
}
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

但是以上代码有可能发生串联。

看以下问题：
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x到点 y 的有向边，边长为 z。
点的编号为 1∼n。

要完成这个问题就要避免串联

怎么保证不发生串联呢？我们保证更新的时候只用上一次循环的结果就行。所以我们先备份一下。备份之后backup数组存的就是上一次循环的结果，我们用上一次循环的结果来更新距离。所以我们这样写dist[b]=min(dist[b],backup[a]+w)来更新距离，而不是dist[b]=min(dist[b],dist[a]+w)，这样写就会发生上面说的”串联”现象。

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=510,M=1e4+10;
int dist[N],backup[N];
int n,m,k;
//这里用结构体存边的信息
struct node
{
    int a,b,c;
}edg[M];
int bellman_ford()
{
    //初始化距离
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++)
    {
        //记得备份，不然会发生串联
        memcpy(backup,dist,sizeof dist);
        //更新所有的边
        for(int j=0;j<m;j++)
        {
            int a=edg[j].a,b=edg[j].b,c=edg[j].c;
            dist[b]=min(dist[b],backup[a]+c);
        }
    }
    return dist[n];
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edg[i]={a,b,c};
    }
    //这里不用0x3f3f3f3f是因为防止n号点被负权边更新
    if(bellman_ford()>0x3f3f3f3f/2)
    cout<<"impossible";
    else
    cout<<dist[n];
    return 0;
}
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

SPFA算法（Bellman-Ford的队列优化）

https://www.luogu.com.cn/problem/P3371

什么是SPFA算法
SPFA 算法是Bellman-ford算法的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。

前置知识：Bellman-ford算法详解_真的没事鸭的博客-CSDN博客

SPFA算法思路
SPFA算法其实就是在Bellman-ford算法基础上的优化。Bellman-ford算法看起来比较傻，每次迭代的话是遍历所有边来更新，但是每次迭代的话不是每条边都会更新。SPFA算法就是对这个做优化，每次迭代dist[b]可以更新的话，一定是dist[a]变小了，因为如果dist[a]不变的话，dist[b]一定不变。只有dist[a]变小了，它的后继才会变小。所以SPFA算法就从这个点进行优化。

SPFA算法的思路就是迭代的时候用一个队列来做，队列里面存的就是到起点距离变小的点。先把起点放到队列里面去，只要队列不空，也就是队列里面还有距离变小的点的话，就执行一下操作：

先取出队头t，然后队头出队
更新t的所有出边，t到起点的距离不是变小了吗， 那么所有和t相连的点都有可能变小，如果更新成功的话，就入队。但是注意要判断一下这个点已经入过队的话就不用重复加入了。
补充
SPFA算法的时间复杂度一般是O(m),最坏情况下时O(nm)。一般正权图我们是用Dijkstra算法去做，但是其实大部分的正权图的问题都可以用SPFA算法来做。不过出题人卡复杂度的话可能就用不了。所以SPFA算法是由Bellman-ford算法优化来的，不过长得特别像Dijkstra算法。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 10005, M = 500005;

const long long INF = 2147483647;
int h[N], ne[M], w[M], e[N], idx = 0;
int dist[N];
int st[N];
int n, m, s;
void add(int a, int b, int c)
{
    ne[idx] = h[a];
    h[a] = idx;
    e[idx] = b;
    w[idx] = c;
    idx++;
}
void spfa(int s)
{

    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    st[s] = 1;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = 0;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            if (dist[e[i]] > dist[t] + w[i])
            {
                dist[e[i]] = dist[t] + w[i];
                if (st[e[i]] == 0)
                {
                    q.push(e[i]);
                    st[e[i]] = 1;
                }
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    memset(st, 0, sizeof(st));
    int a, b, c;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        add(a, b, c);
    }
    spfa(s);
    for (int i = 1; i <= n; i++)
    {
        cout << dist[i] << " ";
    }

    return 0;
}
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