Bellman——Ford算法_bellmanford算法

算法介绍

我们知道Dijkstra算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法就不能帮助我们解决问题了，而本文介绍的bellman—ford算法可以解决负权图且可以判断有无负权回路（迭代超过V-1次，就说明存在负权回路）的单源最短路径问题。

• 它的优点是可以解决有负权边的单源最短路径问题，而且可以用来判断是否有负权回路。
• 它也有明显的缺点，它的时间复杂度 O(N*E) (N是点数，E是边数)普遍是要高于Dijkstra算法O(N²)的。

思路讲解

1. 初始化源点s到各个点v的路径dis[v] = ∞，dis[s] = 0。
2. 进行n - 1次遍历，每次遍历对所有边进行松弛操作，满足则将权值更新。
松弛操作：以a为起点，b为终点，ab边长度为w为例。dis[a]代表源点s到a点的路径长度，dis[b]代表源点s到b点的路径长度。如果满足下面的式子则将dis[b]更新为dis[a] + w。

• dis[b] > dis[a] + w

3. 遍历都结束后，若再进行一次遍历，还能得到s到某些节点更短的路径的话，则说明存在负环路。

案例分析与代码实现

案例分析

先举个栗子：
如下图按Bellman–Ford算法思路获取起点A到终点的最短路径

1.得出边权信息：

A B -1
A C 4
B C 3
B D 2
B E 2
D B 1
D C 5
E D -3

2.首先初始化起点A到各个节点耗费的时间:

3.进行第一次的遍历
(1). 统计经过一条边所能到达的节点的值

A B -1
A C 4

B D 2
B E 2
B C 3

以C节点为例：dis[B] + weight(B -> C) < dis[C]（-1 + 3 < 4）则dis[C] = dis[B] + weight(B -> C)
(3).统计经过三条边所能到达的节点的值

D C 5
D B 1
E D -3

代码实现

#include <iostream>                
#include <string.h>

using namespace std;

#define INF 0x3f
const int a = 2e4+5;

int n,m;
int q,p,w,road[a][a];
int dis[a];
int check = 0;

void BellmanFord()
{
    memset(dis,INF,sizeof(dis));

    dis[1] = 0;

    for(int x = 1; x <= n; x++)
    {
    	check = 0;
        for(int y = 1; y <= m; y++)
        {
            if(dis[y] > dis[x] + road[x][y])
            {
                dis[y] = dis[x] + road[x][y];
                check = 1;
            }
        }
        if(!check)
        {
        	break;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);

    memset(road,INF,sizeof(road));

    for(int x = 1; x <= m; x++)
    {
        scanf("%d%d%d",&q,&p,&w);

        road[q][p] = w;
    }

    BellmanFord();

    for(int x = 2; x <= n; x++)
    {
        printf("%d\n",dis[x]);
    }
}
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

优先队列优化(SPFA)

Bellman—Ford算法的队列优化还有一个名字叫做SPFA(各大竞赛都会进行卡SPFA)。

优化原理

简洁起见，我们约定加权有向图G不存在负权回路，即最短路径一定存在。用数组dis记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

代码实现

#include <iostream>           
#include <algorithm>
#include <string.h>         
#include <queue>

#define inf 1e5+5

using namespace std;

int n,m,s,t;
int vis[1005],cost[1005],h[205];
int tot;

struct Node            //结点信息
{
    int to,w,next;
}road[3000];
struct Node2
{
    int cost1,to;

    friend bool operator < (Node2 x,Node2 y)
    {
        return x.cost1 > y.cost1;
    }
}road1[3000];

void add(int u,int v,int w)           //链式前向星存储邻接表
{
    road[tot].to = v;
    road[tot].w = w;
    road[tot].next = h[u];
    h[u] = tot++;
}

void SPFA(int s)
{
    priority_queue <Node2> pq;

    int e = 0;

    memset(vis,0,sizeof(vis));

    cost[s] = 0;
    road1[e].cost1 = 0;
    road1[e].to = s;
    pq.push(road1[e]);

    while(!pq.empty())
    {
        int x = pq.top().to;
        pq.pop();

        if(vis[x] ++)  continue;

        for(int i = h[x]; i != -1; i = road[i].next)
        {
            int to = road[i].to;

            if(!vis[to] && cost[x] + road[i].w <= cost[to])
            {
                cost[to] = cost[x] + road[i].w;

                e++;
                road1[e].cost1 = cost[to];
                road1[e].to = to;
                pq.push(road1[e]);
            }
        }
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        int u,v,w;
        tot = 0;

        memset(h,-1,sizeof(h));
        for(int x = 0; x < 1005; x++)
        {
            cost[x] = inf;
        }

        for(int i = 0; i < m; i++)
        {
            cin >> u >> v >> w;

            add(u,v,w);
            add(v,u,w);
        }

        cin >> s >> t;

        SPFA(s);

        if(cost[t] == inf)
        {
            cout << -1 << endl;
        }
        else
        {
            cout << cost[t] << endl;
        }
    }
}

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108