算法导论——所有点对的最短路径：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();
		}
	}

}

如果采用负权重环图，则会抛出异常，提示负环并表示无最短路径

如果采用不含负环的图，则会打印如下内容（目前以s=0作测试，其他点作为原点的最短路径可以自行尝试）：

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

原文：http://my.oschina.net/u/1378920/blog/423862