Bellman-Ford算法 (贝尔曼-福特算法)

定义

贝尔曼-福特算法，求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的。

它的原理是对图进行松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高。

原理

Bellman-Ford算法通过松弛（如果 dist[v] < dist[u] + w，则dist[v] = dist[u] + w），反复利用已有的边来更新最短距离。

如果不存在负权回路，应当会在 (n-1) 次松弛之后结束。因为任意两点间的最短路径至多经过 (n-2) 个点，因此经过 (n-1) 次操作后就可以得到最短路径。

如果存在负权回路，那么第 n 次松弛操作仍然会成功，Bellman-Ford算法就是利用这个性质判定负环。

实现

 #include<bits/stdc++.h>
 using   namespace   std;
  const   int  inf= 0x3f3f3f3f  ;
  const   int  maxn= 10005  ;
  struct   node
{
    int   u,v,w;
}edge[maxn];
  int   dis[maxn],n,m;
  int  Bellman_Ford( int   s);
  int   main()
{
    int   i;   
  scanf(  "  %d%d  " ,&n,& m);
    for (i= 1 ;i<=m;i++)  scanf( "  %d%d%d  " ,&edge[i].u,&edge[i].v,& edge[i].w);
    if (Bellman_Ford( 1 )) printf( "  有负环\n  "  );
  system(  "  pause  "  );
    return   0  ;
}
  int  Bellman_Ford( int   s)
{
    int  check,flag= 0  ,i,j;
  fill(dis,dis +maxn,inf);  dis[s]= 0  ;
    for (j= 1 ;j<=n- 1 ;j++ )
  {
    check = 0  ;
      for (i= 1 ;i<=m;i++ )
        if (dis[edge[i].v]>dis[edge[i].u]+ edge[i].w)
      {
        dis[edge[i].v] =dis[edge[i].u]+ edge[i].w;
        check = 1  ;
      }
      if (!check) break  ;
  }

    for (i= 1 ;i<=m;i++ )
      if (dis[edge[i].v]>dis[edge[i].u]+ edge[i].w)
      {
        flag = 1  ;
          break  ;
      }

    if (flag)  return   1  ;
    else 
     for (i= 1 ;i<=n;i++ )
      printf(  "  %d->%d   %d\n  "  ,s,i,dis[i]);
    return   0  ;
}  

查看更多关于Bellman-Ford算法 (贝尔曼-福特算法)的详细内容...