Bellman-Ford单源最短路径算法

Bellman-Ford 算法是一种用于计算带权有向图中单源最短路径（SSSP：Single-Source Shortest Path）的算法。该算法由 Richard Bellman 和 Lester Ford 分别发表于 1958 年和 1956 年，而实际上 Edward F. Moore 也在 1957 年发布了相同的算法，因此，此算法也常被称为 Bellman-Ford-Moore 算法。

Bellman-Ford 算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 \(G = (V, E)\)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。

Bellman-Ford 算法采用动态规划（Dynamic Programming）进行设计，实现的时间复杂度为\(O(V*E)\)，其中 \(V\) 为顶点数量，\(E\) 为边的数量。Dijkstra 算法采用贪心算法（Greedy Algorithm）范式进行设计，普通实现的时间复杂度为 \(O(V^2)\)，若基于 Fibonacci heap 的最小优先队列实现版本则时间复杂度为 \(O(E + VlogV)\)。

Bellman-Ford 算法描述：

1. 创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，初始均为 Infinite，源顶点距离为 0；
2. 计算最短路径，执行 V - 1 次遍历；
   • 对于图中的每条边：如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d，则更新终点 v 的距离值 d；
3. 检测图中是否有负权边形成了环，遍历图中的所有边，计算 u 至 v 的距离，如果对于 v 存在更小的距离，则说明存在环；

代码如下：

struct edge//用来存边
{
    int from;
    int to;
    int cost;
}Edge[M];
int Bellman_Ford(int src, int destination)
{
    // n是节点个数
    vector<vector<int>> dist = vector<int>(k + 1, vector<int>(n, INT_MAX));
    for(int i = 0;i < n; ++i)
        dist[i][0];
    for(int i = 0 ; i < k ; i++)          // 查找从源点开始，经过k个节点可以
    {
        for(int j = 0 ; j < m ; j++)      // m 条边
        {
            int from = Edge[j].from, to = Edge[j].to, cost = Edge[j].cost;
            dist[b] = min(dist[i][to], dist[i - 1][from]);
        }                          
    }
    // dist[k][n]是刚好经过k步到达节点n的最短路径，若为INT_MAX则表示不能到达
    int res = INT_MAX;
    for(int i = 0; i <= k; ++i)
    {
        res = min(res, dist[k][destination]);       // 查找k步内到达destination的最短路径
    }
    // 未考虑负环的存在
    return res == INT_MAX ? -1 : res;    
}