图论

Bellman Ford

Posted by Liao on 2019-09-04

1.定义

     Bellman-Ford 算法是一种用于计算带权有向图中单(一个)源(顶点)最短路径的问题（单源指的是只有一个起点）：给定一个起点，求它到所有结点的最短路径。Bellman-Ford 算法能适应一般的情况（即存在负权边的情况），V*E<10^7。

​ Bellman-Ford 算法采用动态规划进行设计，时间复杂度 O(V*E)，其中 V 为顶点数量，E 为边的数量。

2.算法过程

1）初始化所有点

​ 每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。

2）进入循环

​ 循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。

3）遍历图中所欲边

​ 遍历途中所有的边（edge（u，v）），判断是否存在这样情况： d（v）> d (u) + w(u,v) ，则返回false，表示途中存在从源点可达的权为负的回路。

3.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
#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()
{
    init();
    if(Bellman_Ford())
        for(int i = 1 ;i <= nodenum; i++)
            cout << dist[i] << endl;
    return 0;
}

HDU2544 输入NM，分别是结点的个数和边的个数，以题目第二个样例为例：

2

然后输入两个结点及其两点边的权重。

则通过bellman ford计算出起点到终点的最短路是2。

有帮助的截图

2

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
#include<iostream>
#include<cstdio>
using namespace std;
const int INF = 1e6;
const int NUM = 105;
int n,m,cnt;
struct edge
{
    int u,v,w;  //边:起点 终点 权重
}e[10005];
int pre[NUM];   //记录前驱结点，pre[x]=y 在最短路径上，结点x的前一个结点是y
void bellman()
{
    int s =1;  //定义起点
    int d[NUM];  //d[i]记录第i个结点到起点s的最短距离
    for(int i=1;i<=n;i++)
        d[i] = INF;   //初始化每个结点为无穷大
    d[s] = 0;
    for(int k=1;k<=n;k++)
    {
        for(int i=0;i<cnt;i++)  //检查每条边
        {
            int x = e[i].u;
            int y = e[i].v;
            if(d[x]>d[y]+e[i].w)
            {
                d[x] = d[y]+e[i].w;
//                pre[x] = y;   //记录路径
            }
        }
    }
    printf("%d\n",d[n]);
}
int main()
{
    while(scanf("%d%d",&n,&m) && n && m)
    {
        cnt= 0;
        while(m--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);  //输入两路口（点）、边的权重
            e[cnt].u = a;
            e[cnt].v = b;
            e[cnt].w = c;
            cnt++;
            e[cnt].u = b;
            e[cnt].v = a;
            e[cnt].w = c;
            cnt++;
        }
        bellman();
    }
    return 0;
}

FEATURED TAGS
图论
FRIENDS