即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Dijkstra/ floyd/floyd扩展求最小环/Bellman_Ford(权值可正可负)/SPFA(权值可正可负)判断负环

编程语言 xiangAccepted 15℃ 0评论

最短路径问题旨在寻找图中两节点之间的最短路径常用的算法有以下四种注意是把图处理成无向还是有向





Dijkstra’s (权值非负)


1 Dijkstra’s算法解决的是图中单个源点到其它顶点的最短路径。只能解决权值非负


2 Dijkstral只能求出任意点到达源点的最短距离(不能求出任意两点之间的最短距离),同时适用于有向图和无向图,复杂度为O(n^2).


3算法的过程: 


1设置顶点集合S并不断的作贪心选择来选择扩充这个集合。一个顶点属于集合S当且仅当从源点到该点的最短路径长度已知


2 初始时,S中仅含有源。设U是G的某一个顶点,把从源到U且中间只经过S中的顶点的路称为从源到U的特殊路径,并用dis数组距离当前每一个顶点所对应的最短特殊路径


3Dijkstra算法每一次从V-S中取出具有最短特殊长度的顶点u,将u添加到S中,同时对dis数组进行修改。一旦S包含了所有的V中的顶点,dis数组就记录了从源点到其它顶点的最短路径长度。


4 模板:


没有优化,时间复杂度o(n^2)


  1. #define MAXN 1010   
  2. #define INF 0xFFFFFFF   
  3. int  value[MAXN][MAXN];/*保存的是边权值*/  
  4. int  dis[MAXN];/*保存源点到任意点之间的最短路*/  
  5. int  father[MAXN];/*保存i点的父亲节点*/  
  6. int  vis[MAXN];/*记录顶点是否没取过*/   
  7.   
  8. void input(){       
  9.       int star , end , v;  
  10.       scanf(“%d%d” , &n , &m);  
  11.       /*初始化value数组*/  
  12.      for(int i = 1 ; i <= n ; i++){  
  13.          for(int j = 1; j <= n ; j++)  
  14.              value[i][j] = INF;  
  15.      }  
  16.     for(int i = 0 ; i < m ; i++){  
  17.         scanf(“%d%d%d” ,  &star , &end , &v);  
  18.         if(value[star][end] == INF)  
  19.             value[star][end] = value[end][star] = v;/*处理成无向图*/  
  20.         else{  
  21.             if(v < value[star][end])/*判断重边是否出现*/  
  22.                  value[star][end] = value[end][star] = v;  
  23.         }  
  24. }  
  25.   
  26. void dijkstra(int s){  
  27.      memset(vis , 0 , sizeof(vis));  
  28.      memset(father , 0 , sizeof(father));  
  29.      /*初始化dis数组*/  
  30.      for(int i = 1 ; i<= n ; i++)  
  31.           dis[i] = INF;  
  32.      dis[s] = 0;  
  33.      for(int i = 1 ; i <= n ; i++){/*枚举n个顶点*/  
  34.         int pos;  
  35.         pos = -1;  
  36.         for(int j = 1 ; j <= n ;j++){/*找到未加入集合的最短路点*/  
  37.            if(!vis[j] && (pos == -1 || dis[j] < dis[pos]))  
  38.               pos = j;  
  39.         }  
  40.         vis[pos] = 1;/*把这个点加入最短路径集合*/  
  41.         for(int j = 1 ; j <= n ; j++){/*更新dis数组*/  
  42.            if(!vis[j] && (dis[j] > dis[pos] + value[pos][j])){  
  43.              dis[j] = dis[pos] + value[pos][j];  
  44.              father[j] = pos;  
  45.            }  
  46.         }  
  47.      }  
  48. }  
[cpp] view
plain
 copy

  1. #define MAXN 1010  
  2. #define INF 0xFFFFFFF  
  3. int  value[MAXN][MAXN];/*保存的是边权值*/  
  4. int  dis[MAXN];/*保存源点到任意点之间的最短路*/  
  5. int  father[MAXN];/*保存i点的父亲节点*/  
  6. int  vis[MAXN];/*记录顶点是否没取过*/   
  7.   
  8. void input(){       
  9.       int star , end , v;  
  10.       scanf(“%d%d” , &n , &m);  
  11.       /*初始化value数组*/  
  12.      for(int i = 1 ; i <= n ; i++){  
  13.          for(int j = 1; j <= n ; j++)  
  14.              value[i][j] = INF;  
  15.      }  
  16.     for(int i = 0 ; i < m ; i++){  
  17.         scanf(“%d%d%d” ,  &star , &end , &v);  
  18.         if(value[star][end] == INF)  
  19.             value[star][end] = value[end][star] = v;/*处理成无向图*/  
  20.         else{  
  21.             if(v < value[star][end])/*判断重边是否出现*/  
  22.                  value[star][end] = value[end][star] = v;  
  23.         }  
  24. }  
  25.   
  26. void dijkstra(int s){  
  27.      memset(vis , 0 , sizeof(vis));  
  28.      memset(father , 0 , sizeof(father));  
  29.      /*初始化dis数组*/  
  30.      for(int i = 1 ; i<= n ; i++)  
  31.           dis[i] = INF;  
  32.      dis[s] = 0;  
  33.      for(int i = 1 ; i <= n ; i++){/*枚举n个顶点*/  
  34.         int pos;  
  35.         pos = -1;  
  36.         for(int j = 1 ; j <= n ;j++){/*找到未加入集合的最短路点*/  
  37.            if(!vis[j] && (pos == -1 || dis[j] < dis[pos]))  
  38.               pos = j;  
  39.         }  
  40.         vis[pos] = 1;/*把这个点加入最短路径集合*/  
  41.         for(int j = 1 ; j <= n ; j++){/*更新dis数组*/  
  42.            if(!vis[j] && (dis[j] > dis[pos] + value[pos][j])){  
  43.              dis[j] = dis[pos] + value[pos][j];  
  44.              father[j] = pos;  
  45.            }  
  46.         }  
  47.      }  
  48. }  






  1. 优化过的,时间复杂度为o(mlogn);  
  2. /*利用邻接表来优化*/  
  3. #include    
  4. typedef pair<int , int>pii;/*pair专门把两个类型捆绑在一起的*/  
  5. priority_queue,greater >q;/*优先队列默认使用“<”,那么优先队列的元素是从大到小,所以自己定义“>”比较,STL中可以用greater来表示”>”,这样就可以来声明一个小整数先出队的优先队列*/  
  6. #define MAXN 1010   
  7. #define INF 0xFFFFFFF   
  8. int n , m;/*有n个点,m条边*/  
  9. int first[MAXN] , next[MAXN];/*first数组保存的是节点i的第一条边,next保存的是边e的下一条边*/  
  10. int u[MAXN] , v[MAXN] , value[MAXN];  
  11. int vis[MAXN];  
  12. int dis[MAXN];  
  13.   
  14. /*读入这个图*/  
  15. void input(){  
  16.      scanf(“%d%d” , &n , &m);  
  17.      /*初始化表头*/  
  18.      for(int i = 1 ; i <= n ; i++)  
  19.         first[i] = -1;  
  20.      for(int i = 1 ; i <= m ; i++){  
  21.         scanf(“%d%d” , &u[i] , &v[i] , &value[i]);         
  22.         next[i] = first[u[i]];/*表头往后移动*/  
  23.         first[u[i]] = i;/*更新表头*/  
  24.      }  
  25. }  
  26.   
  27. /*Dijkstra*/  
  28. void Dijkstra(int s){  
  29.      memset(vis , 0 , sizeof(vis));  
  30.      /*初始化点的距离*/  
  31.      for(int i = 1 ; i <= n ; i++)  
  32.           dis[i] = INF;  
  33.     dis[s] = 0;  
  34.      while(!q.empty())  
  35.         q.pop();  
  36.      q.push(make_pair(dis[s] , s));  
  37.      while(!q.empty()){  
  38.           pii u = q.top();  
  39.           q.pop();  
  40.           int x = u.second;  
  41.           if(vis[x])  
  42.             continue;   
  43.           vis[x] = 1;  
  44.           for(int i = first[x] ; i != -1 ; i = next[i]){  
  45.              if(dis[v[e]] > dis[x] + value[i]){  
  46.                 dis[v[i]] = dis[x] + value[i];  
  47.                 q.push(make_pair(dis[v[i] , v[i]));  
  48.              }  
  49.           }  
  50.      }  
  51. }  
[cpp] view
plain
 copy

  1. 优化过的,时间复杂度为o(mlogn);  
  2. /*利用邻接表来优化*/  
  3. #include   
  4. typedef pair<int , int>pii;/*pair专门把两个类型捆绑在一起的*/  
  5. priority_queue,greater >q;/*优先队列默认使用“<”,那么优先队列的元素是从大到小,所以自己定义“>”比较,STL中可以用greater来表示”>”,这样就可以来声明一个小整数先出队的优先队列*/  
  6. #define MAXN 1010  
  7. #define INF 0xFFFFFFF  
  8. int n , m;/*有n个点,m条边*/  
  9. int first[MAXN] , next[MAXN];/*first数组保存的是节点i的第一条边,next保存的是边e的下一条边*/  
  10. int u[MAXN] , v[MAXN] , value[MAXN];  
  11. int vis[MAXN];  
  12. int dis[MAXN];  
  13.   
  14. /*读入这个图*/  
  15. void input(){  
  16.      scanf(“%d%d” , &n , &m);  
  17.      /*初始化表头*/  
  18.      for(int i = 1 ; i <= n ; i++)  
  19.         first[i] = -1;  
  20.      for(int i = 1 ; i <= m ; i++){  
  21.         scanf(“%d%d” , &u[i] , &v[i] , &value[i]);         
  22.         next[i] = first[u[i]];/*表头往后移动*/  
  23.         first[u[i]] = i;/*更新表头*/  
  24.      }  
  25. }  
  26.   
  27. /*Dijkstra*/  
  28. void Dijkstra(int s){  
  29.      memset(vis , 0 , sizeof(vis));  
  30.      /*初始化点的距离*/  
  31.      for(int i = 1 ; i <= n ; i++)  
  32.           dis[i] = INF;  
  33.     dis[s] = 0;  
  34.      while(!q.empty())  
  35.         q.pop();  
  36.      q.push(make_pair(dis[s] , s));  
  37.      while(!q.empty()){  
  38.           pii u = q.top();  
  39.           q.pop();  
  40.           int x = u.second;  
  41.           if(vis[x])  
  42.             continue;   
  43.           vis[x] = 1;  
  44.           for(int i = first[x] ; i != -1 ; i = next[i]){  
  45.              if(dis[v[e]] > dis[x] + value[i]){  
  46.                 dis[v[i]] = dis[x] + value[i];  
  47.                 q.push(make_pair(dis[v[i] , v[i]));  
  48.              }  
  49.           }  
  50.      }  
  51. }  




floyd(权值非负)适用于有向图和无向图


1 floyd 的思想就是通过枚举n个点利用DP的思想来更新最短距离的,假设当前枚举到第k个点,那么就有任意的两个点i , j ,如果i k 相连 j k 相连 那么就可以知道这个时候dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]);,那么只要枚举完n个点,那么就说明已经完全更新完所有两点直间的最短路。


2 floyd算法是最简单的最短路径的算法,可以计算图中任意两点间的最短路径。floyd算法的时间复杂度为o(n^3),如果是一个没有边权的图,把相连的两点间的距离设为dis[i][j]=1.不相连的两点设为无穷大,用floyd算法可以判断i
j两点是否相连。


3 floyd 算法不允许所有的权值为负的回路。可以求出任意两点之间的最短距离。处理的是无向图


4 缺点是时间复杂度比较高,不适合计算大量数据

5 如果dis[i][i] != 0,说明此时存在环。 


6 如果利用floyd求最小值的时候,初始化dis为INF , 如果是求最大值的话初始化为-1.


7 模板:

  1. #define INF 0xFFFFFFF   
  2. #define MAXN 1010   
  3. int dis[MAXN][MAXN];  
  4.   
  5. /*如果是求最小值的话,初始化为INF即可*/  
  6. void init(){  
  7.      for(int i = 1 ; i <= n ; i++){  
  8.         for(int j = 1 ; j <= n ; j++)  
  9.              dis[i][j] = INF;  
  10.         dis[i][i] = 0;  
  11.      }  
  12. }  
  13.   
  14. /*如果是求最大值的话,初始化为-1*/  
  15. void init(){  
  16.      for(int i = 1 ; i <= n ; i++){  
  17.         for(int j = 1 ; j <= n ; j++)  
  18.              dis[i][j] = -1;  
  19.      }  
  20. }  
  21.   
  22. /*floyd算法*/  
  23. void folyd(){  
  24.         for(int k = 1 ; k <= n ; k++){/*枚举n个点来更新dis*/  
  25.             for(int i = 1 ; i <= n ; i++){  
  26.                 for(int j = 1 ; j <= n ; j++)  
  27.                   if(dis[i][k] != -1 && dis[j][k] != -1)/*如果在求最大值的时候加上这一句*/  
  28.                      dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]);   
  29.             }   
  30.        }  
  31.  }  
  32.    
[cpp] view
plain
 copy

  1. #define INF 0xFFFFFFF  
  2. #define MAXN 1010  
  3. int dis[MAXN][MAXN];  
  4.   
  5. /*如果是求最小值的话,初始化为INF即可*/  
  6. void init(){  
  7.      for(int i = 1 ; i <= n ; i++){  
  8.         for(int j = 1 ; j <= n ; j++)  
  9.              dis[i][j] = INF;  
  10.         dis[i][i] = 0;  
  11.      }  
  12. }  
  13.   
  14. /*如果是求最大值的话,初始化为-1*/  
  15. void init(){  
  16.      for(int i = 1 ; i <= n ; i++){  
  17.         for(int j = 1 ; j <= n ; j++)  
  18.              dis[i][j] = -1;  
  19.      }  
  20. }  
  21.   
  22. /*floyd算法*/  
  23. void folyd(){  
  24.         for(int k = 1 ; k <= n ; k++){/*枚举n个点来更新dis*/  
  25.             for(int i = 1 ; i <= n ; i++){  
  26.                 for(int j = 1 ; j <= n ; j++)  
  27.                   if(dis[i][k] != -1 && dis[j][k] != -1)/*如果在求最大值的时候加上这一句*/  
  28.                      dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]);   
  29.             }   
  30.        }  
  31.  }  
  32.    




floyd扩展:





如何用floyd找出最短路径所行经的点: 1 这里要用到另一个矩阵P,它的定义是这样的:p(ij)的值如果为p,就表示i到j的最短行经为i->p…->j,也就是说p是i到j的最短行径中的j之前的第1个点。





2 P矩阵的初值为p(ij) = j。有了这个矩阵之后,要找最短路径就轻而易举了。对于i到j而言找出p(ij),令为p,就知道了路径i->p….->j;再去找p(pj),如果值为q,p到j的最短路径为p->q…->j;再去找p(qj),如果值为r,i到q的最短路径为q>r…->q;所以一再反复,就会得到答案。





3  但是,如何动态的回填P矩阵的值呢?回想一下,当d(ij)>d(ik)+d(kj)时,就要让i到j的最短路径改为走i->…->k->…->j这一条路,但是d(ik)的值是已知的,换句话说,就是i->…->k这条路是已知的,所以i->…->k这条路上k的第一个城市(即p(ik))也是已知的,当然,因为要改走i->…->k->…->j这一条路,p(ij)的第一个城市正好是p(ik)。所以一旦发现d(ij)>d(ik)+d(kj),就把p(ik)存入p(ij).





4 代码:

  1. int dis[MAXN][MAXN];  
  2. int path[MAXN][MAXN];  
  3.   
  4. void floyd(){  
  5.       int  i, j, k;  
  6.       /*先初始化化为j*/  
  7.       for (i = 1; i <= n; i++){  
  8.            for (j = 1; j <= n; j++)  
  9.                path[i][j] = j;  
  10.       }  
  11.       for (k = 1; k <= n; k++){/*枚举n个点*/  
  12.           for (i = 1; i <= n; i++){  
  13.               for (j = 1; j <= n; j++){  
  14.                    if (dis[i][j] > dis[i][k]+dis[k][j]){  
  15.                          path[i][j] = path[i][k];/*更新为path[i][k]*/  
  16.                          dis[i][j] = dis[i][k]+dis[k][j];  
  17.                     }  
  18.               }  
  19.            }  
  20.       }  
  21. }  
[cpp] view
plain
 copy

  1. int dis[MAXN][MAXN];  
  2. int path[MAXN][MAXN];  
  3.   
  4. void floyd(){  
  5.       int  i, j, k;  
  6.       /*先初始化化为j*/  
  7.       for (i = 1; i <= n; i++){  
  8.            for (j = 1; j <= n; j++)  
  9.                path[i][j] = j;  
  10.       }  
  11.       for (k = 1; k <= n; k++){/*枚举n个点*/  
  12.           for (i = 1; i <= n; i++){  
  13.               for (j = 1; j <= n; j++){  
  14.                    if (dis[i][j] > dis[i][k]+dis[k][j]){  
  15.                          path[i][j] = path[i][k];/*更新为path[i][k]*/  
  16.                          dis[i][j] = dis[i][k]+dis[k][j];  
  17.                     }  
  18.               }  
  19.            }  
  20.       }  
  21. }  




2  floyd求解环中的最小环


1 为什么要在更新最短路之前求最小环:


在第k层循环,我们要找的是最大结点为k的环,而此时Dist数组存放的是k-1层循环结束时的经过k-1结点的最短路径,也就是说以上求出的最短路是不经过k点的,这就刚好符合我们的要求。为什么呢?假设环中结点i,j是与k直接相连,如果先求出经过k的最短路,那么会有这样一种情况,即:i到j的最短路经过k。这样的话就形成不了环 。


2最小环改进算法的证明:


一个环中的最大结点为k(编号最大),与他相连的两个点为i,j,这个环的最短长度为g[i][k]+g[k][j]+dis[i][j] (i到j的路径中,所有结点编号都小于k的最短路径长度)。根据floyd的原理,在最外层循环做了k-1次之后,dist[i][j]则代表了i到j的路径中,所有结点编号都小于k的最短路径, 综上所述,该算法一定能找到图中最小环。


3 为什么还要value数组:


因为dis数组时刻都在变动不能表示出原来两个点之间的距离。


4 形成环至少要有3点不同的点,两个点是不能算环的。


5 代码:

  1. int mincircle = INF;  
  2. int dis[MAXN][MAXN];  
  3. int value[MAXN][MAXN];  
  4.   
  5. void floyd(){  
  6.      memcpy(value , dis , sizeof(value));  
  7.      for(int k = 1 ; k <= n ; k++){  
  8.           /*求最小环,不包含第k个点*/  
  9.           for(int i = 1 ; i < k ; i++){/*到k-1即可*/  
  10.                for(int j = i+1 ; j < k ; j++)/*到k-1即可*/  
  11.                    mincircle = min(mincircle , dis[i][j]+value[i][k]+value[k][j]);/*无向图*/  
  12.                    mincircle = min(mincircle , dis[i][j] +value[i][k]+value[k][j]);/*表示i->k , k->j有边*/  
  13.            }  
  14.           /*更新最短路*/  
  15.           for(int i = 1 ; i <= n ; i++){  
  16.                for(int j = 1 ; j <= n ; j++)  
  17.                    dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]);  
  18.           }  
  19.      }    
  20. }  
[cpp] view
plain
 copy

  1. int mincircle = INF;  
  2. int dis[MAXN][MAXN];  
  3. int value[MAXN][MAXN];  
  4.   
  5. void floyd(){  
  6.      memcpy(value , dis , sizeof(value));  
  7.      for(int k = 1 ; k <= n ; k++){  
  8.           /*求最小环,不包含第k个点*/  
  9.           for(int i = 1 ; i < k ; i++){/*到k-1即可*/  
  10.                for(int j = i+1 ; j < k ; j++)/*到k-1即可*/  
  11.                    mincircle = min(mincircle , dis[i][j]+value[i][k]+value[k][j]);/*无向图*/  
  12.                    mincircle = min(mincircle , dis[i][j] +value[i][k]+value[k][j]);/*表示i->k , k->j有边*/  
  13.            }  
  14.           /*更新最短路*/  
  15.           for(int i = 1 ; i <= n ; i++){  
  16.                for(int j = 1 ; j <= n ; j++)  
  17.                    dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]);  
  18.           }  
  19.      }    
  20. }  

Bellman_Ford(权值可正可负),用来判断负环 


1 Bellman_Frod可以计算边权为负值的最短路问题,适用于有向图和无向图.用来求解源点到达任意点的最短路。

2 在边权可正可负的图中,环有零环,正环,负环3种。如果包含零环和正环的话,去掉以后路径不会变成,如果包含负环则最短路是不存在的。那么既然不包含负环,所以最短路除了源点意外最多只经过n-1个点,这样就可以通过n-1次的松弛得到源点到每个点的最短路径。


3 时间复杂度o(n*m);


4 如果存在环的话就是经过n-1次松弛操作后还能更新dis数组。


5 模板:

  1. /* 
  2. 适用条件: 
  3. 1单源最短路径 
  4. 2有向图和无向图 
  5. 3边权可正可负 
  6. */  
  7.   
  8. #define INF 0xFFFFFFF   
  9. #define MAXN 1010*2   
  10. int dis[MAXN];/*dis[i]表示的是源点到点i的最短路*/  
  11. strucu Edge{  
  12.    int x;  
  13.    int y;  
  14.    int value;  
  15. }e[MAXN];  
  16.   
  17. /*返回最小值*/  
  18. int min(int a , int b){  
  19.     return a < b ? a : b;  
  20. }  
  21.   
  22. /*处理成无向图*/  
  23. void input(){  
  24.      for(int i = 0 ; i < m ; i++){  
  25.         scanf(“%d%d%d” , e[i].x , &e[i].y , &e[i].value);  
  26.         e[i+m].x = e[i].y;/*注意地方*/  
  27.         e[i+m].y = e[i].x;/*注意地方*/  
  28.         e[i+m].value = e[i].value;            
  29.      }  
  30. }  
  31.   
  32. /*假设现在有n个点,m条边*/  
  33. void Bellman_Ford(int s){  
  34.     /*初始化dis数组*/  
  35.     for(int i = 1 ; i <= s ; i++)  
  36.          dis[i] = INF;  
  37.     dis[s] = 0;  
  38.     for(int i = 1 ; i < n ; i++){/*做n-1次松弛*/  
  39.        for(int j = 0 ; j < 2*m ; j++){/*每一次枚举2*m条边,因为是无向图*/  
  40.           if(dis[e[j].y] > dis[e[j].x] + e[j].value)  
  41.            dis[e[j.].y] = dis[e[i].x]+e[j].value;/*更新dis[e[j].y]*/  
  42.           }  
  43.        }  
  44.     }  
  45. }  
[cpp] view
plain
 copy

  1. /* 
  2. 适用条件: 
  3. 1单源最短路径 
  4. 2有向图和无向图 
  5. 3边权可正可负 
  6. */  
  7.   
  8. #define INF 0xFFFFFFF  
  9. #define MAXN 1010*2  
  10. int dis[MAXN];/*dis[i]表示的是源点到点i的最短路*/  
  11. strucu Edge{  
  12.    int x;  
  13.    int y;  
  14.    int value;  
  15. }e[MAXN];  
  16.   
  17. /*返回最小值*/  
  18. int min(int a , int b){  
  19.     return a < b ? a : b;  
  20. }  
  21.   
  22. /*处理成无向图*/  
  23. void input(){  
  24.      for(int i = 0 ; i < m ; i++){  
  25.         scanf(“%d%d%d” , e[i].x , &e[i].y , &e[i].value);  
  26.         e[i+m].x = e[i].y;/*注意地方*/  
  27.         e[i+m].y = e[i].x;/*注意地方*/  
  28.         e[i+m].value = e[i].value;            
  29.      }  
  30. }  
  31.   
  32. /*假设现在有n个点,m条边*/  
  33. void Bellman_Ford(int s){  
  34.     /*初始化dis数组*/  
  35.     for(int i = 1 ; i <= s ; i++)  
  36.          dis[i] = INF;  
  37.     dis[s] = 0;  
  38.     for(int i = 1 ; i < n ; i++){/*做n-1次松弛*/  
  39.        for(int j = 0 ; j < 2*m ; j++){/*每一次枚举2*m条边,因为是无向图*/  
  40.           if(dis[e[j].y] > dis[e[j].x] + e[j].value)  
  41.            dis[e[j.].y] = dis[e[i].x]+e[j].value;/*更新dis[e[j].y]*/  
  42.           }  
  43.        }  
  44.     }  
  45. }  




SPFA(权值可正可负),判断负环.


1用来求解单源最短路径,源点到任意点的最短路。


2 算法介绍:建立一个队列q,初始时队列里只有一个起始点,在建立一个数组dis记录起始点到所有点的最短路径,并且初始化这个数组。然后进行松弛操作,用 队列里面的点去刷新起始点到所有点的最短路,如果刷新成功且刷新点不再队列中则把该点加入到队列最后,重复执行直到队列为空。


3 时间复杂度:O(ke),k指的是所有顶点的进队的平均次数,可以证明k<=2,e为边数





4 可以用SPFA来存在是否存在环,如果是的话就是存在一条边的松弛操作大于等于n。


5 模板:

  1. /* 
  2. 1 n个点 m条边 
  3. 2 邻接表存储图: first[i]存储的是节点i的第一条边的编号,nest[i]存储的是编号为i的边的下一条边的编号。 
  4. 3 star[i]表示编号为i的边的起点,end[i]表示编号为i的边的终点,value[i]表示编号为i的边的权值。 
  5. 4 dis[i] 表示的源点到i的最短路 
  6. */  
  7.   
  8. #define MAXN 1010   
  9. #define INF 0xFFFFFFF   
  10.   
  11. int n , m;  
  12. int first[MAXN] , next[MAXN];  
  13. int star[MAXN] , end[MAXN] , value[MAXN];  
  14. int dis[MAXN];  
  15. queue<int>q;  
  16.   
  17. /*输入*/  
  18. void input(){  
  19.      scanf(“%d%d” , &n , &m);  
  20.      /*初始化表头*/  
  21.      for(int i = 1 ; i <= n ; i++){  
  22.         first[i] = -1;  
  23.         next[i] = -1;  
  24.      }  
  25.      /*读入m条边*/  
  26.      for(int i = 0 ; i < m ; i++){  
  27.         scanf(“%d%d%d” , &star[i] , &end[i] , &value[i]);  
  28.         star[i+m] = end[i];  
  29.         end[i+m] = star[i];  
  30.         value[i+m] = value[i];  
  31.   
  32.         next[i] = first[star[i]];/*由于要插入表头,所以将原先表头后移*/  
  33.         first[star[i]] = i;/*插入表头*/  
  34.         next[i+m] = first[star[i+m]];  
  35.         first[star[i+m]] = i+m;  
  36.      }  
  37. }  
  38.   
  39. /*SPFA*/  
  40. void SPFA(int s){  
  41.      while(!q.empty())  
  42.           q.pop();  
  43.      int vis[MAXN];  
  44.      memset(vis , 0 , sizeof(vis));  
  45.      /*初始化dis*/  
  46.      for(int i = 1 ; i <= n ; i++)  
  47.           dis[i] = INF;  
  48.      dis[s] = 0;  
  49.      q.push(s);/*将源点加入队列*/  
  50.      vis[s] = 1;/*源点标记为1*/  
  51.      while(!q.empty()){  
  52.           int x = q.front();  
  53.           q.pop();  
  54.           vis[x] = 0;/*注意这里要重新标记为0,说明已经出队*/  
  55.           /*枚举和点x有关的所有边*/  
  56.           for(int i = first[x] ; i != -1 ; i = next[i]){  
  57.              if(dis[end[i]] > dis[x] + value[i]){/*松弛操作,利用三角不等式*/  
  58.                dis[end[i]] = dis[x] + value[i];  
  59.                if(!vis[end[i]]){/*如果该点不再队列里面*/  
  60.                   vis[end[i]] = 1;                  
  61.                   q.push(end[i]);  
  62.                }  
  63.              }  
  64.           }  
  65.      }  
[cpp] view
plain
 copy

  1. /* 
  2. 1 n个点 m条边 
  3. 2 邻接表存储图: first[i]存储的是节点i的第一条边的编号,nest[i]存储的是编号为i的边的下一条边的编号。 
  4. 3 star[i]表示编号为i的边的起点,end[i]表示编号为i的边的终点,value[i]表示编号为i的边的权值。 
  5. 4 dis[i] 表示的源点到i的最短路 
  6. */  
  7.   
  8. #define MAXN 1010  
  9. #define INF 0xFFFFFFF  
  10.   
  11. int n , m;  
  12. int first[MAXN] , next[MAXN];  
  13. int star[MAXN] , end[MAXN] , value[MAXN];  
  14. int dis[MAXN];  
  15. queue<int>q;  
  16.   
  17. /*输入*/  
  18. void input(){  
  19.      scanf(“%d%d” , &n , &m);  
  20.      /*初始化表头*/  
  21.      for(int i = 1 ; i <= n ; i++){  
  22.         first[i] = -1;  
  23.         next[i] = -1;  
  24.      }  
  25.      /*读入m条边*/  
  26.      for(int i = 0 ; i < m ; i++){  
  27.         scanf(“%d%d%d” , &star[i] , &end[i] , &value[i]);  
  28.         star[i+m] = end[i];  
  29.         end[i+m] = star[i];  
  30.         value[i+m] = value[i];  
  31.   
  32.         next[i] = first[star[i]];/*由于要插入表头,所以将原先表头后移*/  
  33.         first[star[i]] = i;/*插入表头*/  
  34.         next[i+m] = first[star[i+m]];  
  35.         first[star[i+m]] = i+m;  
  36.      }  
  37. }  
  38.   
  39. /*SPFA*/  
  40. void SPFA(int s){  
  41.      while(!q.empty())  
  42.           q.pop();  
  43.      int vis[MAXN];  
  44.      memset(vis , 0 , sizeof(vis));  
  45.      /*初始化dis*/  
  46.      for(int i = 1 ; i <= n ; i++)  
  47.           dis[i] = INF;  
  48.      dis[s] = 0;  
  49.      q.push(s);/*将源点加入队列*/  
  50.      vis[s] = 1;/*源点标记为1*/  
  51.      while(!q.empty()){  
  52.           int x = q.front();  
  53.           q.pop();  
  54.           vis[x] = 0;/*注意这里要重新标记为0,说明已经出队*/  
  55.           /*枚举和点x有关的所有边*/  
  56.           for(int i = first[x] ; i != -1 ; i = next[i]){  
  57.              if(dis[end[i]] > dis[x] + value[i]){/*松弛操作,利用三角不等式*/  
  58.                dis[end[i]] = dis[x] + value[i];  
  59.                if(!vis[end[i]]){/*如果该点不再队列里面*/  
  60.                   vis[end[i]] = 1;                  
  61.                   q.push(end[i]);  
  62.                }  
  63.              }  
  64.           }  
  65.      }  

转载请注明:CodingBlog » Dijkstra/ floyd/floyd扩展求最小环/Bellman_Ford(权值可正可负)/SPFA(权值可正可负)判断负环

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情