单源最短路径（2）：Bellman-Ford算法

一：背景

Dijkstra算法是处理单源最短路径的有效算法，但它对存在负权回路的图就会失效。这时候，就需要使用其他的算法来应对这个问题，Bellman-Ford（中文名：贝尔曼-福特）算法就是其中一个。

Bellman-Ford算法不仅可以求出最短路径，也可以检测负权回路的问题。该算法由美国数学家理查德•贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特•福特（Lester Ford）发明。

二：算法过程分析

对于一个不存在负权回路的图，Bellman-Ford算法求解最短路径的方法如下：

设其顶点数为n，边数为m。设其源点为source，数组dist[i]记录从源点source到顶点i的最短路径，除了dist[source]初始化为0外，其它dist[]皆初始化为MAX。以下操作循环执行n-1次：

• 对于每一条边arc(u, v)，如果dist[u] + w(u, v) < dist[v]，则使dist[v] = dist[u] + w(u, v)，其中w(u, v)为边arc(u, v)的权值。

n-1次循环，Bellman-Ford算法就是利用已经找到的最短路径去更新其它点的dist[]。

接下来再看看Bellman-Ford算法是如何检测负权回路的？

检测的方法很简单，只需在求解最短路径的n-1次循环基础上，再进行第n次循环：

• 对于所有边，只要存在一条边arc(u, v)使得dist[u] + w(u, v) < dist[v]，则该图存在负权回路，其中w(u, v)为边arc(u, v)的权值。

三：完整代码

#include <iostream>
#include <stack>

using namespace std;

#define MAX 10000  // 假设权值最大不超过 10000

struct Edge
{
    int u;
    int v;
    int w;
};

Edge edge[10000]; // 记录所有边
int  dist[100];   // 源点到顶点 i 的最短距离
int  path[100];   // 记录最短路的路径
int  vertex_num;  // 顶点数
int  edge_num;    // 边数
int  source;      // 源点

bool BellmanFord()
{
    // 初始化
    for (int i = 0; i < vertex_num; i++)
        dist[i] = (i == source) ? 0 : MAX;

    // n-1 次循环求最短路径
    for (int i = 1; i <= vertex_num - 1; i++)
    {
        for (int j = 0; j < edge_num; j++)
        {
            if (dist[edge[j].v] > dist[edge[j].u] + edge[j].w)
            {
                dist[edge[j].v] = dist[edge[j].u] + edge[j].w;
                path[edge[j].v] = edge[j].u;
            }
        }
    }

    bool flag = true;  // 标记是否有负权回路

    // 第 n 次循环判断负权回路
    for (int i = 0; i < edge_num; i++)
    {
        if (dist[edge[i].v] > dist[edge[i].u] + edge[i].w)
        {
            flag = false;
            break;
        }
    }

    return flag;
}

void Print()
{
    for (int i = 0; i < vertex_num; i++)
    {
        if (i != source)
        {
            int p = i;
            stack<int> s;
            cout << "顶点 " << source << " 到顶点 " << p << " 的最短路径是： ";

            while (source != p)  // 路径顺序是逆向的，所以先保存到栈
            {
                s.push(p);
                p = path[p];
            }

            cout << source;
            while (!s.empty())  // 依次从栈中取出的才是正序路径
            {
                cout << "--" << s.top();
                s.pop();
            }
            cout << "    最短路径长度是：" << dist[i] << endl;
        }

    }
}

int main()
{

    cout << "请输入图的顶点数，边数，源点：";
    cin >> vertex_num >> edge_num >> source;

    cout << "请输入" << edge_num << "条边的信息：\n";
    for (int i = 0; i < edge_num; i++)
        cin >> edge[i].u >> edge[i].v >> edge[i].w;

    if (BellmanFord())
        Print();
    else
        cout << "Sorry,it have negative circle!\n";

    return 0;
}

运行截图：

四：算法优化

以下除非特殊说明，否则都默认是不存在负权回路的。

先来看看Bellman-Ford算法为何需要循环n-1次来求解最短路径？

读者可以从Dijkstra算法来考虑，想一下，Dijkstra从源点开始，更新dist[]，找到最小值，再更新dist[] ，，，每次循环都可以确定一个点的最短路。Bellman-Ford算法同样也是这样，它的每次循环也可以确定一个点的最短路，只不过代价很大，因为Bellman-Ford每次循环都是操作所有边。

既然代价这么大，相比Dijkstra算法，Bellman-Ford算法还有啥用？因为后者可以检测负权回路啊。

Bellman-Ford算法的时间复杂度为$O(nm)$，其中n为顶点数，m为边数。

$O(nm)$的时间，大多数都浪费了。考虑一个随机图（点和边随机生成），除了已确定最短路的顶点与尚未确定最短路的顶点之间的边，其它的边所做的都是无用的，大致描述为下图（分割线以左为已确定最短路的顶点）：

其中红色部分为所做无用的边，蓝色部分为实际有用的边。