`
128kj
  • 浏览: 604163 次
  • 来自: ...
社区版块
存档分类
最新评论

图解Bellman-Ford算法

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











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


     Bellman-Ford算法主要是针对有负权值的图。来判断该图中是否有负回路,或者存在最短路径的点。判断的思路,从源点出发,进行n - 1(n为顶点数)遍历,在每次的遍历过程中,对所有的边进行遍历判断,同样是利用松弛计算的思想,dis[v] > dis[u] + w(u, v)不断更新dis数组的值,直到循环结束。然后就是这个算法最精彩的地方了,再对所有的边进行一次遍历,看是否存在dis[v] > dis[u] + w(u, v)的边,若存在,则返回FALSE,说明图中存在负回路;若不存在,则返回TRUE,dis数组记录的就是每一个点到源点的最小值。


例:求如图中A点到各点的最短距离


  
/** 
 * 采用保存边的方式来存储图的的信息。 
 * p保存的是前驱节点,d保存的是源点到每一个点的最短距离。我们最后又做了一次判断,如果还有可以松弛 
 * 的边,那么可以保证的是图中有负权的环存在,这样的话就没有最短路径只说了,可以无限小。 
 *  
 * @author daijope 
 * 
 */  
public class BellmanFord {  
    private static final int m = 10000;  
    public static void main(String[] args) {  
          
        Adge a1 = new Adge(0, 1, -1);  
        Adge a2 = new Adge(0, 2, 4);  
        Adge a3 = new Adge(1, 2, 3);   
        Adge a4 = new Adge(3, 1, 1);  
        Adge a5 = new Adge(1, 3, 2);  
        Adge a6 = new Adge(3, 2, 5);  
        Adge a7 = new Adge(1, 4, 2);  
        Adge a8 = new Adge(4, 3, -3);  
        Adge[] as = new Adge[]{a1, a2, a3, a4, a5, a6, a7, a8};  
          
        int[] d = new int[5];  
        int[] p = new int[5];  
        d[0] = 0;  
        p[0] = 0;  
        for (int i = 1; i < d.length; i++) {  
            d[i] = m;  
            p[i] = -1;  
        }  
        bellman_Ford(as, d, p);  
          
        for (int i = 0; i < d.length; i++) {  
            System.out.println(d[i]);  
        }  
    }  
    private static void bellman_Ford(Adge[] as, int[] d, int[] p){  
        for(int i = 1; i < d.length; i++) {  
            for (int j = 0; j < as.length; j++) {  
                if (d[as[j].getV()] > d[as[j].getU()] + as[j].getW()) {  
                    d[as[j].getV()] = d[as[j].getU()] + as[j].getW();  
                    p[as[j].getV()] = as[j].getU();  
                }  
            }  
        }  
        for (int j = 0; j < as.length; j++) {  
            if (d[as[j].getV()] > d[as[j].getU()] + as[j].getW()) {  
                System.out.println("有负环");  
            }  
        }  
  
          
    }  
}  
class Adge {  
    private int u;  
    private int v;  
    private int w;  
      
    public Adge(int u, int v, int w) {  
        this.u = u;  
        this.v = v;  
        this.w = w;  
    }  
  
    public int getU() {  
        return u;  
    }  
  
    public void setU(int u) {  
        this.u = u;  
    }  
  
    public int getV() {  
        return v;  
    }  
  
    public void setV(int v) {  
        this.v = v;  
    }  
  
    public int getW() {  
        return w;  
    }  
  
    public void setW(int w) {  
        this.w = w;  
    }  
      
      
}  


运行:
C:\java>java   BellmanFord
0
-1
2
-2
1

下载源码
  • 大小: 38.8 KB
  • 大小: 25.2 KB
  • 大小: 11.2 KB
  • 大小: 7 KB
  • 大小: 36.9 KB
分享到:
评论

相关推荐

    算法伪代码以及常用图示_V1.0.pdf

    Dijkstra算法是一种用于在加权图中找到单源最短路径的算法,与Bellman-Ford算法不同的是,Dijkstra算法假设所有边的权重都是非负的。算法通过维护一个距离集合来不断更新节点到源点的最短距离,并使用一个优先队列来...

    差分约束系统详解.doc

    求解差分约束问题时,可以利用图算法,比如 Bellman-Ford 算法。由于在约束图中 v0 可以到达所有其他顶点,所以如果算法表明没有负权回路,那么最短路径的权值就给出了一个可行解。如果算法检测到负权回路,则表示...

    数据结构算法图解

    最后,图论中的算法如最短路径算法(Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法)、最小生成树算法(Prim算法、Kruskal算法)和拓扑排序在网络路由、资源分配等问题中有着广泛应用。 这些图解资源将帮助...

    python算法.zip

    - Bellman-Ford算法:处理可能有负权重边的最短路径问题。 - Kruskal和Prim算法:最小生成树问题,用于寻找连接所有顶点的权值最小的边集合。 4. **动态规划**: - 背包问题:0-1背包、完全背包和多重背包,寻找...

    Dijkstra算法图解.docx

    * Bellman-Ford算法:用于解决负权边的问题。 * Floyd-Warshall算法:用于解决所有节点之间的最短路径问题。 Dijkstra算法是一种经典的图搜索算法,具有广泛的应用前景。通过了解算法的原理和实现,可以更好地理解...

    求最短路径算法

    最短路径算法还有其他变种和扩展,比如Floyd-Warshall算法适用于求解所有对之间最短路径,而Bellman-Ford算法则可以处理含有负权边的图。理解并掌握这些算法对于解决实际的网络问题、优化路线规划、数据传输等问题至...

    用图示法解析最短路径算法

    为了求解最短路径问题,学者们提出了多种算法,包括著名的迪杰斯特拉(Dijkstra)算法、贝尔曼-福特(Bellman-Ford)算法、弗洛伊德(Floyd-Warshall)算法、A*搜索算法等。这些算法各有其适用的场景和优缺点。 ...

    和小浩学算法.zip

    3. 图算法:如深度优先搜索(DFS)、广度优先搜索(BFS)、最短路径算法(Dijkstra、Floyd-Warshall、Bellman-Ford)等,这些算法在处理网络结构问题时非常有用,例如在地图导航、社交网络分析等领域。 4. 动态规划:这是...

    《剑指 Offer》 Python, Java, C++ 解题代码,LeetBook《图解算法数据结构》配套代码仓.zip

    8. **图论**:包括最短路径算法(Dijkstra、Bellman-Ford)、最小生成树(Prim、Kruskal)等,适用于网络流问题和关系分析。 9. **位操作**:在 Python、Java 和 C++ 中,位操作可以用于高效地处理整数,尤其在解决...

    数学建模~最短路问题(课件ppt).ppt

    这种问题可以使用 Dijkstra 算法或 Bellman-Ford 算法来解决。 每对顶点之间的最短路问题是指在图中寻找每对顶点之间的最短路。这种问题可以使用 Floyd-Warshall 算法来解决。 四、 最小生成树问题 最小生成树...

    初中数学中最短路径问题专题教学设计(推荐).pdf

    这个问题可以通过多种算法来解决,比如迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd-Warshall)算法、贝尔曼-福特(Bellman-Ford)算法等。在初中教学中,可能会采用更为直观和易于理解的方法来引导学生探索。 在...

    《运筹学》_练习卷一、二、三_-_答案.pdf

    解这类问题可以使用标号法,如Dijkstra算法或Bellman-Ford算法。 8. **松弛变量**:在线性规划中,松弛变量用于将不等式约束转换为等式,使问题更容易求解。 9. **名词解释**: - **需求**:在库存管理中,需求指...

    运筹学2015学年期末考试题(卷)A卷与答案.doc

    - 最短路径问题:包括定步数和不定步数问题,不定步数问题的求解方法包括迭代法,如Dijkstra算法和Bellman-Ford算法。 5. 判断题: - 单纯形法迭代过程:从一个可行解到目标函数值更大的另一个可行解,但不是每次...

    数据结构例题及参考答案

    2. 最短路径问题:Dijkstra算法和Floyd-Warshall算法用于求解单源最短路径,Bellman-Ford算法则能处理负权边。 四、栈与队列 1. 栈:栈是一种后进先出(LIFO)的数据结构,常用于表达式求值、函数调用等场景。 2. ...

    数学建模算法

    - **Bellman-Ford算法**: 可处理负权边的情况。 **§4 树** - **定义**: 树是一种特殊的图结构,无环且连接所有节点。 - **应用场景**: 如生成树、最小生成树等。 **§5 匹配问题** - **定义**: 在一个二分图中...

    北京科技大学研究生运筹学全套课件.zip

    3. **网络流理论**:如最大流最小割定理,Ford-Fulkerson算法,以及Edmonds-Karp算法等,用于解决网络中的流量分配问题。 4. **图论与网络优化**:介绍图的基本概念,最小生成树(Kruskal和Prim算法),最短路径...

    leetcode卡-python-leetcode:python-leetcode

    6. **图论算法**:深度优先搜索(DFS)、广度优先搜索(BFS)、最短路径问题(Dijkstra、Bellman-Ford)、最小生成树(Prim、Kruskal)等。 7. **字符串处理**:模式匹配、字符串反转、正则表达式等。 8. **位操作...

    数学建模算法大全

    这类问题通常可以通过匈牙利算法或Ford-Fulkerson算法来解决。 综上所述,《数学建模算法大全》涵盖了线性规划、整数规划、非线性规划、动态规划以及图与网络模型等多个领域的数学建模方法和技术。通过对这些知识点...

    运筹学课件--ppt

    "第4章 网络分析.ppt"和"(5.15)第4章 网络分析.ppt"可能包含了网络模型的构建、Dijkstra算法、Ford-Fulkerson算法等内容,这些知识在物流、交通规划等领域有广泛的应用。 动态规划是一种解决多阶段决策问题的方法,...

Global site tag (gtag.js) - Google Analytics