Bellman-Ford算法

Bellman-Ford一般很少用来打题（初赛就不一定了），不是很重要，重要的是它的优化SPFA (虽然它死得很惨)，还有Dijkstra算法（更重要，因为题目一般会卡SPFA

说句题外话，Bellman-Ford=铃铛人-福特 (假的

S P F A 讲解入口(虽然它死了

Dijkstra讲解入口(重难点

蒟蒻正在施工（填坑）中。。。。。。

但不管怎么说，看了Bellman-Ford对于初赛以及对加深(SPFA)的理解有很大的帮助，所以还是很有必要整理一下的！！！

算法概览：

Bellman算法的核心在于它的松弛操作，松弛的意思大概指的就是不断地一点点地优化。重难点就在于遍历过程。具体算法如下：

松弛的含义：

松弛操作的含义大概是：从一个顶点开始将搜索路径发散出去以搜查每一条边，从起点开始，每搜一层都需要把这一层的所有数据更新，如原本从起点到 (A) 的最优解是 (5)，到 (B) 的最优解是 (2) ，(A) 到 (B) 有一条长度为 (2) 的路径，那么也就是说从起点到 (B) 的最优解就可以从原本到 (B) 的最优解 (5)，变成先走最优路径到点 (A) 再经过点 (A) 到 (B) 的那条路径从而更新最优解为 (4).

[ ext{算法导论的图讲得很好了(也是重点了！！！} ]

遍历：

遍历的顺序总是让人摸不着头脑，那么这里分析一下：

STEP.1 初始化

初始化数组，由于是查找最小值，所以要初始化为一个很大的值（这很好理解），这个极大值还表示了两点间没有（或者说暂时没有）通路。

STEP.2 遍历

遍历的顺序与节点无关，与边有关，在遍历的时候需要讨论的是每条边的起点和终点的值。在这里就是通过起点（假设就是上面的那个 (A) 点）对终点（即 (B) 点）进行松弛，那么也就是用状态转移方程：(dis_x=min(dis_y+edgeval,dis_x))
对于每一条边，我们至少要重复遍历 (n-1) 遍：当你运气最不好时，答案的最短路也许是经过每一个其他点最后才回到终点的，这么理解就能很快地得出必须要循环 (n-1) 次让它一步步地从起点走到终点。

图例：

1. x 表示 B 点
2. y 表示 A 点
3. edgeval 表示 A --> B 边的值
4. n 表示 节点个数

STEP.3 负权回路（负环）

负权回路就是因为走了一圈发现你的值在这个圈里面可以无限变小，所以最小值就变成了(-∞)（因为这里有可能有负数）。判断负环操作也很简单实际上就是看看循环完以后有没有不符合的地方，因为负环在不断地变小的时候总会有先有后，在整个环的运算中，出现了前面的减小而后面的相对于前面变大了，当环回来的时候这里“后面的”也就变成了“前面的”，这是矛盾的，所以就能发现这里有负环存在：就像走环形的楼梯总会在头尾相接的地方总会有一个高度差。通过这样判断只要在(n-1)次遍历(int)没有炸，负权就能通过判断最短路的合法性判断出来。（事实上数据很难把(int)炸掉，不行就(long long)，别加(unsigned)就行！

那么最后上代码(网上复制的，等后面两个再自己打~懒):

/*
* About:  Bellman-Ford算法
* Author: Tanky Woo
* Blog:   www.WuTianqi.com
*/

#include 
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()
{
    //freopen("input3.txt", "r", stdin);
    init();
    if(Bellman_Ford())
        for(int i = 1 ;i <= nodenum; i++)
            cout << dist[i] << endl;
    return 0;
}

填坑第 (huge{2}) 站完成！！！

//Good luck