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

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

摘要: 算法导论之FloydWarshall算法

求一个图中任意两点之间的最短路径

FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径

如果普通求最短路径，可以对图进行V次（顶点数）BellmanFord算法。 这样http://的话时间复杂度为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

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 返回类型

* @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

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持!

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 返回类型

* @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

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持!

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。