摘要: 算法导论之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();
}
}
}
如果采用负权重环图，则会抛出异常，提示负环并表示无最短路径
如果采用不含负环的图，则会打印如下内容（目前以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
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持!
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：notice#niaoge.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。