Catshao

用户名：Catshao

访问量：28865

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7135
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

vector、deque、list的速度和内存的比较
浏览：555

Dotcpp编程2021年七月月赛题面
浏览：740

2021七月月赛总结
浏览：195

你可能喜欢

bellman_ford详解（C++代码）（小白向）

　　作者: Catshao　　　　发表时间：2021-02-04 17:37:05 浏览：286　|　评论：0　

原题链接：最短路练习

# Part -1 前置解法

在学习bellman_ford之前，你需要学习**存储图的方法**。
建议在学习bellman_ford之前学习dijkstra，可以参考[程序员小灰的文章](https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653197626&idx=1&sn=fca7472af006a7f8890ee84ad7cf1116&chksm=8c99e7e0bbee6ef6faa1a34160a5e135503425e37552e90dfca2fbc10f223dbf3b875e84e418)

# Part 1 概述

bellman_ford（贝尔曼福德）是一种求**单源最短路**的算法。

#### 单源最短路

单源最短路，即为从**单一定点**，到其他点的最短路径问题。两个节点的最短路问题也属于单源最短路问题。

#### 与dijkstra的区别

优：**dijkstra不能处理负边**，但bellman_ford可以处理负边，针对某些题只能使用bellman_ford（[**多源最短路请看johnson**](https://blog.dotcpp.com/a/76336)）
劣：dijkstra的效率比bellman_ford**快很多**，而且**bellman_ford很容易被卡**

## 过程

- 循环n - 1次：
 - 枚举所有边
   - 如果`边的起点距离 + 边长 < 边的终点距离` 那么 更新`边的终点距离`。
   (距离，都是指**最短路起点**到另一个点的距离)

其中的判断，被称为**松弛**。

![过程](http://cat-shao.gitee.io/mypic/relax.png)

整个bellman_ford的过程就像**一滴墨水滴到了水池中，不断扩散，直到填满整个图**。这个过程需要多久呢？从起点开始，即使整个图像一条链一样，也只需要`n - 1`次。

#### 负环

但是，前文说过，bellman_ford是可以处理负边的。

![过程](http://cat-shao.gitee.io/mypic/fuhuan.png)

上面这个图，程序会一直绕下去，因为转完一圈距离反而更小了，我们对这种现象称为**负环**。

前面说过，最多只需要更新`n - 1`次，那么，如果在`第n次`更新了，必然是图中有负环。由于负环可以一直绕下去，所以**有负环的图最短路是无解的**

#### 减少计算

前面说过，最多会更新`n - 1`，但是有的时候并不需要更新这么多次，所以我们需要一个变量`update`来记录下当前一轮是否更新了，如果第i轮没有更新，那么`i + 1 ~ n - 1`次必然不会更新，退出即可。

#### 时间复杂度

需要枚举每一条边，需要枚举`n-1`，所以时间复杂度大概为`O(VE)`，v为节点数（vertex），e为边（edge）。

## 本题代码

```
#include <cstdio>
#include <deque>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

const long long INF = INT_MAX;
const int MAX_N = 100;

class edge {
public:
    int to;
    long long cost;
    edge() {
    }

edge(int _to, long long _cost) {
        to = _to;
        cost = _cost;
    }

bool operator < (const edge &e) const {
        return cost > e.cost;
    }
};

typedef deque<edge> graphType;

bool bellmanFord(graphType graph[], long long dis[], int n, int s)
{
    fill(dis, dis + MAX_N, INF); // 初始化距离为无限
    dis[s] = 0; // 起点到自己距离为0
    for (int k = 1; k <= n; ++k) {
        bool update = false; // 判断是否更新
        for (int i = 1; i <= n; ++i) { // 枚举每一条边
            for (graphType::iterator it = graph[i].begin(); it != graph[i].end(); it++) {
                if (dis[i] + it->cost < dis[it->to]) { // 松弛
                    dis[it->to] = dis[i] + it->cost;
                    update = true;
                    if (k == n) { // 第n次还在更新，有负环
                        return false;
                    }
                }
            }
        }
        if (!update) {
            return true;
        }
    }
    return true;
}

int bellmanFordMain() // https://www.dotcpp.com/oj/problem1708.html题目的main函数
{
    long long dis[MAX_N];
    int path[MAX_N];
    graphType graph[MAX_N];

int n, m, s;
    scanf("%d%d", &n, &s);
    s++;

for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &m);
            if (m) {
                graph[i].push_back(edge(j, m));
            }
        }
    }

bellmanFord(graph, dis, n, s);
    for (int i = 1; i <= n; ++i) {
        if (i == s) {
            continue;
        }
        if (dis[i] != INF) {
            printf("%d ", dis[i]);
        } else {
            printf("-1 ");
        }
    }
    return 0;
}

int main()
{
    long long dis[MAX_N];
    int path[MAX_N];
    graphType graph[MAX_N];

int n, m;
    scanf("%d", &n);

for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &m);
            if (m) {
                graph[i].push_back(edge(j, m));
            }
        }
    }

bellmanFord(graph, dis, n, 1);
    printf("%d", dis[n]);
    return 0;
}
```

--------------------
bellman_ford还有很多其他的优化，比如LLL优化与堆优化，但是bellman_ford优化后速度仍然没有dijkstra快~~，所以传统武功，点到为止~~。

参考：无。

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

弟弟的作业（C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

（格式错误） qq290048663 碰巧告知我吧

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

bellman_ford详解（C++代码）（小白向）

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

钟神赛车（C++代码）

字符串对比（C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

弟弟的作业 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

（格式错误） qq290048663 碰巧告知我吧

产生数 （C++代码）（大数乘法也是可以避免的么hhhh）

bellman_ford详解（C++代码）（小白向）

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

钟神赛车 （C++代码）

字符串对比 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

弟弟的作业（C语言代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

　　评论区

钟神赛车（C++代码）

字符串对比（C语言代码）