最简单的最短路算法

金克拉好处都有啥~

• 可判负环
• 单源最短路径

吐槽

• =W= 一个小时才完全搞明白mX,Xm自己浪费时间有点多

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3;
const int INF = 9999;
typedef struct{
    int a,b,w;
}Edge;
int dist[N];
Edge edge[N]; // 定义边
int n,m,cnt;
bool bellman_ford(int u ){
    dist[u] = 0;
  for (int i = 1; i < n; i++){
    bool flag = false; //剪枝
    for (int j = 0; j < m; j++){
        if(dist[edge[j].b] > dist[edge[j].a]+ edge[j].w){
              dist[edge[j].b]   =  dist[edge[j].a]+ edge[j].w;
              flag = true;
        }
    }
    if(!flag) return false;
  }

  /*验证是否有负环*/
  for (int j = 0; j< m; j++)
  {
     if(dist[edge[j].b] > dist[edge[j].a]+ edge[j].w){
              return true;
     }
  }
  cout <<"JoJo这是我的逃跑路线！！" << endl; // 测试BUG
  return false;
}
int main(){

 cout << "请输入有多少个节点和多少条边：";
 cin >> n >> m;
 cnt = 0;
 cout << "请按边进行输入 格式为 起点 终点 权值:" << endl;

 for (int i = 1; i <= m ; i++)
 {
    int a,b,w;
    cin >> a>> b >> w;
    edge[cnt].a= a;
    edge[cnt].b = b;
    edge[cnt].w = w;
    cnt++;
 }
for(int i = 1; i <= n;i++){
        dist[i] = INF;
        // cout <<"到达 "<< i << "距离" <<dist[i] << endl;
}

 if (bellman_ford(1))
 {
    cout << "我去有负环！！！"<<endl;
 }else{
    cout <<"起点：" << 1 <<" 最短距离："<<endl;
    for(int i = 1; i <= n;i++){
        cout <<"到达 "<< i << "距离" <<dist[i] << endl;
    }
 }
 


 
 
}