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 j路径中的一个中间点
  for (int i = 0; i  d[i][k] + d[k][j]) {
   d[i][j] = d[i][k] + d[k][j];
   prev[i][j]=k;
   }
  }
  }
 }

 //四舍五入距离
 for (int i = 0; i i的距离d[i][i]，如果存在小于0的，表示这个i->i的环路的权重和形成了一个负值，也就是存在这个负权重
 //在之前的其他最短路径算法中，无法通过这个方法来检测负环，因为之前路径距离都是保存在一个一维数组中，相等于只能检测d[0][0]，无法检测每个d[i][i]
 for(int i=0;ib最短路径的距离
 * @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 返回类型
 * @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 

0到0的距离为:0.0
0->0

0到1的距离为:0.93
0->2->7->3->6->4->5->1
0到2的距离为:0.26
0->2
0到3的距离为:0.99
0->2->7->3
0到4的距离为:0.26
0->2->7->3->6->4
0到5的距离为:0.61
0->2->7->3->6->4->5
0到6的距离为:1.51
0->2->7->3->6
0到7的距离为:0.6
0->2->7