Go语言视频零基础入门到精通

javalearner

一、Bellman-Ford算法：
      为了能够求解边上带有负值的单源最短路径问题，Bellman(贝尔曼)和Ford(福特)提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度的方法。

     Bellman-ford算法是求解连通带权图中单源最短路径的一种常用算法，它允许图中存在权值为负的边。 同时它还能够判断出图中是否存在一个权值之和为负的回路。如果存在的话，图中就不存在最短路径(因为，假设存在最短路径的话，那么我们只要将这条最短路径沿着权值为负的环路再绕一圈，那么这条最短路径的权值就会减少了，所以不存在最短的路径，因为路径的最小值为负无穷），如果不存在的话，那么求出源点到所有节点的最短路径。  
  
  
   
   

     
   

     
   
  
二、Bellman-Ford算法的限制条件：
   要求图中不能包含权值总和为负值回路(负权值回路)，如下图所示。



三、Bellman-Ford算法思想






四、图例



五：算法实现

1. static final int MAX=99999;
   
2. int Edge[][];        //图的邻接矩阵
   
3. int vexnum;        //顶点个数
   
4.   private void BellmanFord(int v) {//假定图的邻接矩阵和顶点个数已经读进来了
   
5.         int i, k, u;
   
6.         for(i=0; i< vexnum; i++){
   
7.            dist[i]=Edge[v][i];        //对dist[]初始化
   
8.            if( i!=v && dis[i]< MAX ) path[i] = v;//对path[ ]初始化
   
9.            else path[i] = -1;
   
10.         }
    
11.         //如果dist[]各元素的初值为MAX，则循环应该n-1次，即k的初值应该改成1。
    
12.   for(k=2; k< vexnum; k++){ //从dist(1)[u]递推出dist(2)[u], …,dist(n-1)[u]
    
13.         for(u=0; u< vexnum; u++){//修改每个顶点的dist[u]和path[u]
    
14.           if( u != v )        {
    
15.        for(i=0; i< vexnum; i++){//考虑其他每个顶点
    
16.                 if( Edge[i][u]< MAX &&dist[u]>dist[i]+Edge[i][u] ){
    
17.                    dist[u]=dist[i]+Edge[i][u];
    
18.                    path[u]=i;
    
19.                 }
    
20.       }
    
21.      }
    
22.         }
    
23.    }
    
24. }
    

复制代码

五、Dijkstra算法与Bellman算法的区别
      Dijkstra算法和Bellman算法思想有很大的区别：
Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到T集合中各顶点的最短路径长度。

Bellman算法在求解过程中，每次循环都要修改所有顶点的dist[]，也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来。
     如果存在从源点可达的负权值回路，则最短路径不存在，因为可以重复走这个回路，使得路径无穷小。 在Bellman算法中判断是否存在从源点可达的负权值回路的方法：

1. for (i=0;i< n;i++){
   
2.   for (j=0;j< n;j++){
   
3.     if (Edge[i][j]< MAX && dist[j]>dist[i]+Edge[i][j])
   
4.           return false;//存在从源点可达的负权值回路
   
5.    }
   
6. }
   
7. return true;
   

复制代码

下载Bellman-Ford算法PPT



  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/4/000807640.zip