Bellman-Ford最短路径算法

谁借莪１个温暖的怀抱￠ 2022-07-12 09:08 191阅读 0赞

原文地址:http://blog.csdn.net/sunnyyoona/article/details/45222073

https://my.oschina.net/u/1378920/blog/421768

**单源最短路径**

给定一个图,和一个源顶点src,找到从src到其它所有所有顶点的最短路径，图中可能含有负权值的边。

Dijksra的[算法][Link 1]是一个贪婪算法,时间复杂度是O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在有负权值边的图中不适用,Bellman-Ford适合这样的图。在网络路由中，该算法会被用作距离向量路由算法。

Bellman-Ford也比迪杰斯特拉算法更简单和同时也适用于分布式系统。但Bellman-Ford的**时间复杂度是O(VE)**,这要比迪杰斯特拉算法慢。（V为顶点的个数,E为边的个数）

**算法描述**

输入:图 和 源顶点src  
输出:从src到所有顶点的最短距离。如果有负权回路(不是负权值的边),则不计算该最短距离，没有意义，因为可以穿越负权回路任意次，则最终为负无穷。

**算法步骤**

1.初始化：将除源点外的所有顶点的最短距离估计值 dist\[v\] ← +∞, dist\[s\] ←0;  
2.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）  
3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 dist\[v\]中。

关于该算法的证明也比较简单，采用反证法，具体参考： [http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf][http_courses.csail.mit.edu_6.006_spring11_lectures_lec15.pdf]  
该算法是利用 **动态规划**的思想。该算法以自底向上的方式计算最短路径。  
它首先计算最多一条边时的最短路径(对于所有顶点)。然后,计算最多两条边时的最短路径。外层循环需要执行|V|-1次。

**例子**

一下面的有向图为例：给定源顶点是0，初始化源顶点距离所有的顶点都是是无穷大的,除了源顶点本身。因为有5个顶点，因此所有的边需要处理4次。

![这里写图片描述][20150423150946160]

按照以下的顺序处理所有的边：(B,E), (D,B), (B,D), (A,B), (A,C), (D,C), (B,C), (E,D).  
第一次迭代得到如下的结果(第一行为初始化情况,最后一行为最终结果)：

当 (B,E), (D,B), (B,D) 和 (A,B) 处理完后，得到的是第二行的结果。  
当 (A,C) 处理完后，得到的是第三行的结果。  
当 (D,C), (B,C) 和 (E,D) 处理完后，得到第四行的结果。

![这里写图片描述][20150423151138845]

第一次迭代保证给所有最短路径最多只有1条边。当所有的边被第二次处理后，得到如下的结果(最后一行为最终结果)：

![这里写图片描述][20150423151048295]

第二次迭代保证给所有最短路径最多只有2条边。我们还需要2次迭代(即所谓的松弛操作)，就可以得到最终结果。

public class BellmanFord {
    
    	// 原点
    	private int s;
    
    	// 从原点到达i的距离为dist[i]
    	private double dist[];
    
    	// 最短路径的前驱节点
    	private int[] prev;
    
    	// 是否含有负权重环，默认false表示不含有
    	private boolean negativeCycle;
    
    	public BellmanFord(WeightDigraph g, int s) {
    
    		int v = g.v();
    		this.s = s;
    
    		dist = new double[v];
    		prev = new int[v];
    
    		for (int i = 0; i < v; i++) {
    			dist[i] = Double.POSITIVE_INFINITY;
    			prev[i] = -1;
    		}
    
    		/**
    		 * 由于最短路径一定是一条不含有环的简单路径 1.如果有正环，一定不是最短路径 2.如果是0环，可以去掉改环多余部分也不影响
    		 * 3.如果是负环，则表示不存在最短路径
    		 * 
    		 * 简单路径中，数量为V的元素个数形成的最短路径有为V-1个边，对所有边进行V-1次更新，会得到所有点的最短路径
    		 */
    		// 不含有负环，所以s->s的最短路径当然为0
    		dist[s] = 0;
    
    		for (int i = 0; i < v - 1; i++) {
    			for (int m = 0; m < v; m++) {
    				relax(m, g);
    			}
    		}
    
    		/**
    		 * 在完成了v-1次全部边更新之后，理应无法继续更新，因为已经找到了s距离每个点的最短路径，如果还能继续更新，说明该图中含有负环。
    		 * 一旦该图含有负环，则表示可以无限次更新下去，也就是说该图根本不存在最短路径
    		 */
    
    		for (int m = 0; m < v; m++) {
    			for (Edge edge : g.adj(m)) {
    				int n = edge.otherSide(m);
    
    				if (dist[n] > dist[m] + edge.weight()) {
    					// 含有负权重环
    					negativeCycle = true;
    					return;
    				}
    			}
    		}
    
    	}
    
    	private void relax(int m, WeightDigraph g) {
    		for (Edge edge : g.adj(m)) {
    			int n = edge.otherSide(m);
    
    			if (dist[n] > dist[m] + edge.weight()) {
    				dist[n] = dist[m] + edge.weight();
    				prev[n] = m;
    			}
    		}
    	}
    
    	/**
    	 * 
    	 * @Title: distTo
    	 * @Description: s->d的最短距离
    	 * @param @param d
    	 * @param @return 设定文件
    	 * @return double 返回类型
    	 * @throws
    	 */
    	public double distTo(int d) {
    		return dist[d];
    	}
    
    	/**
    	 * 
    	 * @Title: hasPathTo
    	 * @Description: s->d是否存在可达路径
    	 * @param @param d
    	 * @param @return 设定文件
    	 * @return boolean 返回类型
    	 * @throws
    	 */
    	public boolean hasPathTo(int d) {
    		return distTo(d) < Double.POSITIVE_INFINITY;
    	}
    
    	/**
    	 * 
    	 * @Title: pathTo
    	 * @Description: s->d的最短路径
    	 * @param @param d
    	 * @param @return 设定文件
    	 * @return Iterable<Integer> 返回类型
    	 * @throws
    	 */
    	public Iterable<Integer> pathTo(int d) {
    		if (!hasPathTo(d))
    			return null;
    		Stack<Integer> path = new Stack<Integer>();
    
    		for (int i = d; i != -1; i = prev[i]) {
    			path.push(i);
    		}
    
    		return path;
    	}
    
    	public static void main(String[] args) {
    		//不含负权重环的文本数据
    		String text1="F:\\算法\\attach\\tinyEWDn.txt";
    		//含有负权重环的文本数据
    		String text2="F:\\算法\\attach\\tinyEWDnc.txt";
    		WeightDigraph g = new WeightDigraph(new In(text1
    				));
    		BellmanFord d = new BellmanFord(g, 0);
    
    		if (d.negativeCycle) {
    			System.out.println("该有向加权图含有负权重环，不存在最短路径");
    		} else {
    			for (int i = 0; i < g.v(); i++) {
    				Iterable<Integer> path = d.pathTo(i);
    				if (path == null) {
    					System.out.println("从原点" + d.s + "到" + i + "没有可达路径");
    				} else {
    					System.out.println("从原点" + d.s + "到" + i + "的最短距离为："
    							+ d.distTo(i));
    					System.out.print("路径为：");
    					for (int j : d.pathTo(i)) {
    						System.out.print(j + "->");
    					}
    					System.out.println();
    				}
    			}
    		}
    	}
    }

[Link 1]: http://lib.csdn.net/base/datastructure
[http_courses.csail.mit.edu_6.006_spring11_lectures_lec15.pdf]: http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf
[20150423150946160]: /images/20220710/c9dd603bc18c44c48a0f089d1593378b.png
[20150423151138845]: /images/20220710/2ca588f1ad18483e826a7cd66171ce1f.png
[20150423151048295]: /images/20220710/cbc5ff07f0a14ac28c43fe3d95fe22da.png