No.6.3 最短路径之Bellman-Ford算法--解决负权边

一、无论Floyd还是Dijkstra,算法的假设前提就是,没有负权边。

但是Bellman-Ford算法可以:

  if( dis[v[i]] > dis[u[i]] + w[i])

    dis[v[i]] = dis[u[i]] + w[i];

  u[i], v[i], w[i] 分别记录一条边的起点,终点,边长;dis[x] 表示源点 1 到 顶点 x 的最短距离;

  那么算法的意思就是:如果通过顶点 u[i] 使得 源点 1 到 顶点 v[i] 的距离变短,那么执行Dijkstra的“松弛“操作!

过程:

  1.先按照给定边的顺序松弛,这时表示的是源点 1 ,只能经过一条边时,到达其他各点的最短路径;

  2.重复松弛,这时表示的是源点 1 ,经过 2<= k <= n-2 条边时(n个节点之间最多n-1条边,仅需松弛循环n-2次),可到达其他各点的最短路径;

  3.k>=n的可能性(回路):如果是正权回路,那么越走越远;如果是负权回路,则没有最短路径。所以不可能有最短路径中不可能有回路;

 

二、code

int main(){
  int i,j,n,m;
  int dis[10];
  int inf=999999;
  int u[10],v[10],w[10];

  scanf("%d %d",&n,&m); //n=点数,m=边数

  for(i=1;i<=m;i++){
    scanf("%d %d %d",&u[i],&v[i],&w[i]);
  }


  for(i=1;i<=n;i++)
    dis[i]=inf;
  dis[1]=0;

  for(i=1;i<=n-1;i++){     //Bellman-Ford 算法核心
    for(j=1;j<=m;j++){   //松弛的对象是边,不是点!
      if(dis[v[j]] > dis[u[j]] + w[j])
        dis[v[j]] = dis[u[j]] + w[j];
    }
  }

  //如果n-1轮松弛之后,最短路径依然会发生变化,说明该图存在负权回路!
  for(i=1;i<=m;i++)
    if(dis[v[i]] > dis[u[i]] + w[i])
      printf("图中存在负权回路");

  for(i=1;i<=n;i++)
    printf("%d\t",dis[i]);

  getchar();getchar();return 0;
}

算法的时间复杂度为O(NM),对于稀疏图来说,比Dijkstra要高效的多!

 

上一篇:基础算法学习--Bellman_ford算法


下一篇:Bellman-Ford算法