bellman - ford

刺骨的言语ヽ痛彻心扉 2021-06-22 15:37 163阅读 0赞

什么是bellman - ford算法？
    可以用来求不超过k条边（有负权边）的最短路，也可以求是否存在负环
    ，但时间复杂度较高，因此其他求存在负边的最短路，一般用spfa算法
    Bellman - ford算法是求含负权图的单源最短路径的一种算法，
    其原理为遍历所有的边连续进行松弛，在每次松弛时把每条边都更新一下，
    若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果
    (通俗的来讲就是：假设1号点到n号点是可达的，遍历所有的点，
    更新相邻的点的最短距离，通过循环n-1次操作，若图中不存在负环，
    则1号点一定不会到达n号点，若图中存在负环，则在n-1次松弛后一定还会更新)
    bellman - ford算法的具体步骤
    
    for n次
    for 所有边 a,b,w (松弛操作)
    dist[b] = min(dist[b],backup[a] + w)
    
    注意：backup[]数组是上一次迭代后dist[]数组的备份，
    由于每一次迭代的时候可能更新其他边的长度超过了题目限制的k值，因此需要对dist[]数组进行备份，
    用上一次的dist[]来更新最短距离若不进行备份会因此发生串联效应，影响到下一个点
    在下面代码中，是否能到达n号点的判断中需要进行if(dist[n] > 0x3f3f3f3f/2)判断，而并非是if(dist[n] == 0x3f3f3f3f)判断，
    原因是0x3f3f3f3f是一个确定的值，可能存在某个点q不能由1来更新本身的距离为0x3f3f3f3f但是dist[n]可以用q来更新，因此dist[n]的值可能小于0x3f3f3f3f，但是不会太小，因此可以写成判断小于 0x3f3f3f3f/2。
    bellman - ford只需要遍历所有边就行了因此定义一个结构体就可以了

#include <iostream>
    #include <algorithm>
    #include <queue>
    #include <cstring>
    #include <map>
    using namespace std;
    const int maxn=1e4+10;

struct edges{ 
    	int a,b,w;
    }edges[maxn];//边的个数 
    int dist[maxn],backup[maxn];
    //由于连锁关系，所以需要进行备份操作
    //使用backup数组的目的是为了防止松弛的次数大于k
    int n,m,k;

int bellman_ford(){ 
    	 memset(dist,0x3f,sizeof(dist));
    	 //初始化距离,0x3f而不要初始化成太小的
    	 dist[1]=0;
    	 //松弛k次
    	 for(int i=0;i<k;i++){ 
    	 	 memcpy(backup,dist,sizeof(dist));
    	 	 for(int j=0;j<m;j++){ //遍历所有边 
    	 	 	 auto e=edges[j];
    	 	 	 dist[e.b]=min(dist[e.b],backup[e.a]+e.w);//更新 
    		  }
    	 }
    	 if(dist[n]>0x3f3f3f3f/2){ 
    	 	return -1;
    	 }
    	 else{ 
    	 	return dist[n];
    	 }	 
    	 
    }

int main()
    { 
    
    	cin>>n>>m>>k;
      for(int i=0;i<m;i++){ 
      	 cin>>edges[i].a>>edges[i].b>>edges[i].w;
      }
       if( bellman_ford()==-1){ 
         	cout<<"impossible"<<endl;
    		  
    	 }
    	 else{ 
    	 	cout<< bellman_ford();
    	 }
       
    
    	return 0;
    }