Bellman-ford算法（贝尔曼-福特算法）（邻接表）（C++实现）

实现代码

#include<bits/stdc++.h>
using namespace std;

const int INF = 0xFFFF;


struct Edge{
    int to;
    int weight;
};

vector< vector<Edge> > adjancentList;
vector<int> path;
vector<int> dist;

bool bellmanFord(int source, int vexNum) {
    dist.resize(vexNum);
    //dist数组初始化为源点source到其邻接顶点的边权值
    //若为不是源点source的邻接点则dist对应值为无穷大
    for (int i = 0; i < vexNum; i++) {
        dist[i] = INF;
    }
    dist[source] = 0;
    for (int j = 0; j < adjancentList[source].size(); j++) {
        if (dist[adjancentList[source][j].to] > dist[source] + adjancentList[source][j].weight) {
            dist[adjancentList[source][j].to] = dist[source] + adjancentList[source][j].weight;
            path[adjancentList[source][j].to] = source;
        }
    }
    for (int i = 0; i < vexNum; i++) {
        for (int j = 0; j < adjancentList[i].size(); j++) {
            if (dist[adjancentList[i][j].to] > dist[i] + adjancentList[i][j].weight) {
                dist[adjancentList[i][j].to] = dist[i] + adjancentList[i][j].weight;//更新dist数组
                path[adjancentList[i][j].to] = i;//更新路径
            }
        }
    }
    //判定负权环
    //对每个顶点为绕行点的路径更新后，若网中不存在负权环则无法再缩减距离
    //即dist[i] + adjancentList[i][j].weight不变
    //若dist[i] + adjancentList[i][j].weight减少则表明存在负权环
    //由于adjancentList[i][j].weight保持不变，而dist[i]在负权环中被更新
    //遍历所有的边，若第n次操作仍然可以降低开销，则说明存在负权环
    for (int i = 0; i < adjancentList.size(); i++) {
        for (int j = 0; j < adjancentList[i].size(); j++) {
            if (dist[adjancentList[i][j].to] > dist[i] + adjancentList[i][j].weight) {
                return false;
            }
        }
    }
    return true;
}

int main(int argc, char const *argv[])
{
    int from, to;
    int weight;
    int vexNum;
    int source;
    if(argc == 1){
        argv[1] = "Bellman-Ford.txt";
    }
    freopen(argv[1], "r", stdin);
    scanf("%d%d", &vexNum, &source);
    adjancentList.resize(vexNum);
    path.resize(vexNum);
    while(~scanf("%d%d%d", &from, &to, &weight)) {
        adjancentList[from - 1].push_back((Edge){to - 1, weight});
    }
    if (bellmanFord(source - 1, vexNum)) {
        printf("Bellman-ford path\n");
        for (int i = 0; i < path.size(); i++) {
            printf("%d ", path[i]);
        }
        printf("\nBellman-ford edges weight\n");
        for (int i = 0; i < dist.size(); i++) {
            printf("%d ", dist[i]);
        }
    } else {
        printf("Negative circle exists!");
    }
    return 0;
}

算法思路

百度百科Bellman-Ford算法

• 松弛
  每次松弛操作实际上是对相邻节点的访问，第 n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过 |V|-1条边，所以可知贝尔曼-福特算法所得为最短路径。
• 负边权操作
  与迪科斯彻算法不同的是，迪科斯彻算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。
• 负权环判定
  因为负权环可以无限制的降低总花费，所以如果发现第 n次操作仍可降低花销，就一定存在负权环。

思路

• 负权环
  负权环是指环的累积边权值小于零的环
• 负权环导致的问题
  当且仅当存在负权环导致在广度寻找最短路径的过程中会不断更新dist数组，不断降低边的累计权值，最短路径累积边权值将会为无穷大
• 负权环的判定
  对每个顶点为绕行点的路径更新后，若网中不存在负权环则无法再缩减距离，即dist[i] + adjancentList[i][j].weight不变，若dist[i] + adjancentList[i][j].weight减少则表明存在负权环，由于adjancentList[i][j].weight保持不变，而dist[i]在负权环中被更新。故遍历所有的边，若第n次操作仍然可以降低开销，则说明存在负权环。
• 上述代码已在重要的代码部分添加了相应注释，构造网等部分的代码不再赘述
• Bellman-ford算法的时间复杂度为O(|V|·|E|)
• 样例与Dijkstra，Floyd等算法的样例相似，再次便不再赘述
• Dijkstra算法
• Floyd算法

测试数据1

3 1
1 2 -1
2 3 -1
3 1 6
2 1 1
1 3 4

输出结果1

Bellman-ford path
0 0 1
Bellman-ford edges weight
0 -1 -2

测试数据2

3 1
1 2 -1
2 3 -10
3 1 6
2 1 1
1 3 4

输出结果

Negative circle exists!

鸣谢

感谢百度百科提供的百科知识

最后

• Bellman-ford算法优于Dijkstra算法的方面是边的权值可以为负数、实现简单，但其时间复杂度过高
  算法时间复杂度O(|V|·|E|)
• 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！