Bellman-ford - Githubissues

适用条件&范围：

单源最短路径(从源点s到其它所有顶点v);
有向图&无向图(无向图可以看作$(u,v),(v,u)$同属于边集E的有向图);
边权可正可负(如有负权回路输出错误提示);
差分约束系统;

Bellman-Ford算法的流程如下：

给定图$G(V, E)$（其中$V、E$分别为图$G$的顶点集与边集），源点$s$，数组$Distant[i]$记录从源点s到顶点i的路径长度，初始化数组$Distant[s]$为0；
以下操作循环执行至多$n-1$次，$n$为顶点数：
- 对于每一条边$e(u, v)$，如果$Distant[u] + w(u, v) < Distant[v]$，则 $Distant[v] = Distant[u]+w(u, v)$。其中$w(u, v)$为边$e(u,v)$的权值；
- 若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；
对于每一条边$e(u, v)$，如果存在$Distant[u] + w(u, v) < Distant[v]$的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组$Distant[n]$中记录的就是源点$s$到各顶点的最短路径长度。

*可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为$O(VE)$.**

Bellman－Ford算法可以大致分为三个部分

第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为 0，其它的点的值设为无穷大（表示不可达）。
第二，进行循环，循环下标为从1到$n-1$（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
第三，遍历途中所有的边$edge（u，v）$，判断是否存在这样情况： $d（v） > d (u) + w(u,v)$ 则返回false，表示途中存在从源点可达的权为负的回路。

之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则应为无法收敛而导致不能求出最短路径。

与dij的比较

在更新路径的操作上，和迪杰斯特拉算法大同小异，但是不同于迪杰斯特拉算法，他不是选取最小的边进行选择，而是根据每一条边，依次对Distence数组进行更新，所以会访问很多访问过的点，借此重复不遗漏的更新距离数组，也就是规划起点到当前访问的相邻点的问题。

核心代码：

struct Node{
    int v,dis;
};
vector<Node> Adj[MAXV];
int n;
int d[MAXV];

bool Bellman(int s){
    fill(d,d+MAXV,INF);
    d[s]=0;
    for(int i=0;i<n-1;i++){
        for(int u=0;u<n;u++){
            for(int j=0;j<Adj[u].size();j++){
                int v=Adj[u][j].v;
                int dis=Adj[u][j].dis;
                if(d[u]+dis<d[v]){
                    d[v]=d[u]+dis;
                }
            }
        }
    }
    for(int u=0;u<n;u++){
            for(int j=0;j<Adj[u].size();j++){
                int v=Adj[u][j].v;
                int dis=Adj[u][j].dis;
                if(d[u]+dis<d[v]){
                    return false;
            }
        }
    }
    return true;
}

Caaaa-a / 1

Bellman-ford #6

适用条件&范围：

Bellman-Ford算法的流程如下：

Bellman－Ford算法可以大致分为三个部分

与dij的比较

核心代码：