- 浏览: 583984 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
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点到各点的最短距离
运行:
C:\java>java BellmanFord
0
-1
2
-2
1
下载源码
为了能够求解边上带有负值的单源最短路径问题,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
下载源码
发表评论
-
龙抬头
2014-11-10 15:06 551... -
求推箱子的最小步数(java)
2014-05-06 08:32 3661题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1527POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2982POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
图的练习题(有解答)
2012-12-27 22:23 26141. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2406//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1841经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
2012-11-13 19:02 2742POJ1734 题意:给定一个N个点的无向图,求一个最小环(各 ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3112回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1774一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9551如图:求出有向图的所有环。 import java.uti ... -
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
2012-11-05 13:15 1778题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1301Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1866很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1400Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1354题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1534拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3987一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1786无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 4965prim算法是用来实现图最小生成树的2种常用方法之一,P ...
相关推荐
bellman-ford算法的C++实现,邻接表
Bellman-Ford算法与差分约束系统
Java实现的Dijkstra算法和Bellman-ford算法代码,带UI界面,已封装的可执行jar文件,以及源代码。
分步介绍了bellman-ford算法的详细步骤和分析方法,最后给出了例题进行了说明
受求解最短路径问题的Bellman-Ford算法的启发,我们证明了所提出的路径公式可以被广义Bellman-Ford算法有效地求解。为了进一步提高路径表示的能力,我们提出了神经BellmanFord网络(NBFNet),这是一个通用的图神经...
Bellman-Ford算法是一种用于计算图中单源最短路径的算法,可以处理带有负权边的图。使用Python实现了这个算法。 Bellman-Ford算法是一种用于计算图中单源最短路径的算法,它可以处理带有负权边的图。以下是Bellman-...
基于Bellman-Ford最短路径算法的演示程序 提供源代码
最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(CC++),希望对你能有所帮助!
Bellman-Ford——解决负权边
Bellman-Ford模板 Bellman-Ford模板 Bellman-Ford模板 Bellman-Ford模板 Bellman-Ford模板
Bellman-Ford 算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E),Dijkstra 算法要求图 G 中边的权值均为非负,而 Bellman-Ford 算法能适应一般的情况(即存在负权边的情况)。一个实现的...
经典算法书籍《算法导论》之图算法章节中Bellman-ford算法的C++版。
Bellman-Ford算法(单源最短路径) 矩阵是在main函数里输入的 可以处理带负权的图
Bellman-ford算法.ppt
Bellman-Ford算法.docx
蓝桥杯CJ2-11-图论最短路径问题 Bellman-Ford算法+SPFA.pdf
图论- 最短路- Bellman-Ford 算法与 SPFA.rar
Bellman-Ford算法性能可移植的GPU并行优化.pdf
bellman-Ford算法的具体实现,用c++的语法实现,简单易懂。