Bellmanford算法（负边权最短路径）

---

弥补了Dijskla的缺陷：

A->B的Dijskla算法在出现负数的时候出现判断错误。

image.png
image.png

---

问题的原因：

之所以出现问题不是因为有负值出现，而是因为有负环出现。

以上面的情况为例：

1. 第一轮刚开始：

image.png

2. 第一轮遍历结束：

image.png

3. 第二轮结束：

每遍历一次最短路径就会比原来少一点，无法稳定。

image.png

---

优化的SPFA（Shortest Path Faster）算法：

• 如果有闭环，则dis[choosed]>distance总需要不断更新。总是会有新的节点push然后pop，最后陷入死循环，直到counts[choosed]>=点数，触发警告跳出循环，因为入栈次数最多不超过点数（即最高为points-1）。

• 如果没闭环，则dis[choosed]>distance更新停止。不会有新的节点进入，pop之后empty退出循环。

---

时间复杂度为O(K*E)，E为边数，K为一个常数，通常小于等于2。

需要的标记量：

queue<int>q;            // 缓存已占领的节点队列
int dis[N]={0};           // 记录到源点的距离
bool occupy[N]={false};   // 是否在queue中
int counts[N]={0};        // 计算同一个节点的入栈次数，>=n即有负环出现，return ;

示例代码：

#include <bits/stdc++.h>
using namespace std;
typedef struct{
  int num;      // 在BFS中第一列[0]中作为记录上次遍历的位置
  int length;    // 长度
}Node;
#define N 100000
int dis[N]={0};           // 记录到源点的距离
bool occupy[N]={false};   // 是否在queue中
int counts[N]={0};        // 计算同一个节点的入栈次数，>=n即有负环出现，return ;
int points=0;             // 记录点数
int edges=0,begining,ending;
vector<vector<Node>>v;
// 思路：BFS暴力穷举所有的边，进行全局优化。
int bellman(vector<vector<Node>>v,int begining){
  int i=0,j=0;
  queue<int>q;
  q.push(begining);
  counts[begining]++;
  // 入栈时访问计数器++

  while(!q.empty()){
    int t=q.front();
    q.pop();
    occupy[t]=false;
    // 标记为出栈

    for(i=0;i<v[t].size();i++){
      int choosed=v[t][i].num;
      if(!occupy[choosed]){
        int distance=dis[t]+v[t][i].length;
        if(dis[choosed]>distance){
          occupy[choosed]=true;
          // 标记入栈
          q.push(choosed);
          counts[choosed]++;
          // 入栈计数器++
          dis[choosed]=distance;
          // 更新路径

          // 入栈次数>=点数则报错
          if(counts[choosed]>=points){
            return 2;
          }
        }
      }
    }
  }
  return 1;
}
void insert(vector<vector<Node>>&v,int point1,int point2,int length){
  Node node;
  node.num=point2;
  node.length=length;
  v[point1].push_back(node);
}
int main(){
  int i,j;
  scanf("%d %d %d %d",&points,&edges,&begining,&ending);
  int point1,point2,length;
  for(i=0;i<points;i++){
    dis[i]=N;
    vector<Node>vv;
    v.push_back(vv);
  }
  dis[begining]=0;
  // 起始点的距离设为0，其他设为无穷大。
  for(i=0;i<edges;i++){
    scanf("%d %d %d",&point1,&point2,&length);
    insert(v,point1,point2,length);
  }
  int ans=bellman(v,begining);
  cout<<"ans:"<<ans<<endl;
  if(ans==2){
    cout<<"Has negative ring!"<<endl;
    return 0;
  }
  cout<<"-------"<<endl;
  for(i=0;i<points;i++){
    cout<<">>>"<<dis[i]<<" ";
  }
}

/*
3 3 0 2
0 1 5
1 2 3
2 0 -10
*/