java算法导论之FloydWarshall算法实现代码

    FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径         如果普通求最短路径，可以对图进行V次（顶点数）BellmanFord算法。 这样的话时间复杂度为EV^2        如果是稀疏图，则近似于V^3        但是如果是密集图，则时间复杂度会近似达到V^4，这种情况需要优化，这里FloydWarshall通过动态规划进行优化        ，并且使用邻接矩阵来表示图。

package org.loda.graph;import java.math.BigDecimal;import java.math.RoundingMode;import org.loda.util.In;/** *  * @ClassName: FloydWarshall * @Description: 求一个图中任意两点之间的最短路径 *  *        FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径 *  *        如果普通求最短路径，可以对图进行V次（顶点数）BellmanFord算法。 这样的话时间复杂度为EV^2 *        如果是稀疏图，则近似于V^3 *        但是如果是密集图，则时间复杂度会近似达到V^4，这种情况需要优化，这里FloydWarshall通过动态规划进行优化 *        ，并且使用邻接矩阵来表示图。  *         d(i,j); if m=0  *        D(i,j,m)={ *         min(D(i,m,m-1)+D(m,j,m-1),D(i,j,m-1)); if m!=0 * @author minjun * @date 2015年6月1日 上午9:39:42 *  */public class FloydWarshall { private double[][] d; private int[][] prev; private int v; private boolean negativeCycle; public FloydWarshall(int v) { this.v = v; d = new double[v][v]; prev = new int[v][v]; // 默认设置所有节点都不可达，而自己到自己是可达并且距离为0.0 for (int i = 0; i < v; i++) {  for (int j = 0; j < v; j++) {  d[i][j] = Double.POSITIVE_INFINITY;  prev[i][j] = -1;  if(i==j){   d[i][j] = 0;  }  } } } /** *  * @Title: findShortestPath * @Description: 查询最短路径 * @param 设定文件 * @return void 返回类型 * @throws */ public void findShortestPath() { //查找最短路径 for (int k = 0; k < v; k++) {  //将每个k值考虑成i->j路径中的一个中间点  for (int i = 0; i < v; i++) {  for (int j = 0; j < v; j++) {   //如果存在使得权重和更小的中间值k，就更新最短路径为经过k的路径   if (d[i][j] > d[i][k] + d[k][j]) {   d[i][j] = d[i][k] + d[k][j];   prev[i][j]=k;   }  }  } } //四舍五入距离 for (int i = 0; i < v; i++) {  for (int j = 0; j < v; j++) {  d[i][j] = new BigDecimal(d[i][j]).setScale(2,   RoundingMode.HALF_UP).doubleValue();  } } //检测负权重环的方式很简单，就是判断所有i->i的距离d[i][i]，如果存在小于0的，表示这个i->i的环路的权重和形成了一个负值，也就是存在这个负权重 //在之前的其他最短路径算法中，无法通过这个方法来检测负环，因为之前路径距离都是保存在一个一维数组中，相等于只能检测d[0][0]，无法检测每个d[i][i] for(int i=0;i<v;i++){  if(d[i][i]<0)  negativeCycle=true; } } /** *  * @Title: hasNegativeCycle * @Description: 是否拥有负权重环 * @param @return 设定文件 * @return boolean 返回类型 * @throws */ public boolean hasNegativeCycle() { return negativeCycle; } /** *  * @Title: distTo * @Description: a->b最短路径的距离 * @param @param a * @param @param b * @param @return 设定文件 * @return double 返回类型 * @throws */ public double distTo(int a, int b) { if (hasNegativeCycle())  throw new RuntimeException("有负权重环，不存在最短路径"); return d[a][b]; }  /** *  * @Title: printShortestPath * @Description: 打印a->b最短路径 * @param @return 设定文件 * @return Iterable<Integer> 返回类型 * @throws */ public boolean printShortestPath(int a,int b){ if (hasNegativeCycle()){  System.out.print("有负权重环，不存在最短路径"); }else if(a==b)  System.out.println(a+"->"+b); else{  System.out.print(a+"->");  path(a,b);  System.out.print(b); } return true; } private void path(int a, int b) { int k=prev[a][b];  if(k==-1){  return; }  path(a,k); System.out.print(k+"->"); path(k,b); }   /** *  * @Title: addEdge * @Description: 添加边 * @param @param a * @param @param b * @param @param w 设定文件 * @return void 返回类型 * @throws */ public void addEdge(int a, int b, double w) { d[a][b] = w; } public static void main(String[] args) { // 不含负权重环的文本数据 String text1 = "F://算法//attach//tinyEWDn.txt"; // 含有负权重环的文本数据 String text2 = "F://算法//attach//tinyEWDnc.txt"; In in = new In(text1); int n = in.readInt(); FloydWarshall f = new FloydWarshall(n); int e = in.readInt(); for (int i = 0; i < e; i++) {  f.addEdge(in.readInt(), in.readInt(), in.readDouble()); } f.findShortestPath(); int s = 0; for (int i = 0; i < n; i++) {  System.out.println(s + "到" + i + "的距离为:" + f.distTo(s, i));  f.printShortestPath(s, i);  System.out.println(); } }}

0到0的距离为:0.00->00到1的距离为:0.930->2->7->3->6->4->5->10到2的距离为:0.260->20到3的距离为:0.990->2->7->30到4的距离为:0.260->2->7->3->6->40到5的距离为:0.610->2->7->3->6->4->50到6的距离为:1.510->2->7->3->60到7的距离为:0.60->2->7