java算法导论之FloydWarshall算法实现代码
摘要:算法导论之FloydWarshall算法
求一个图中任意两点之间的最短路径
FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径 如果普通求最短路径，可以对图进行V次（顶点数）BellmanFord算法。这样的话时间复杂度为EV^2 如果是稀疏图，则近似于V^3 但是如果是密集图，则时间复杂度会近似达到V^4，这种情况需要优化，这里FloydWarshall通过动态规划进行优化 ，并且使用邻接矩阵来表示图。
实例代码：
packageorg.loda.graph;
importjava.math.BigDecimal;
importjava.math.RoundingMode;
importorg.loda.util.In;
/**
*
*@ClassName:FloydWarshall
*@Description:求一个图中任意两点之间的最短路径
*
*FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径
*
*如果普通求最短路径，可以对图进行V次（顶点数）BellmanFord算法。这样的话时间复杂度为EV^2
*如果是稀疏图，则近似于V^3
*但是如果是密集图，则时间复杂度会近似达到V^4，这种情况需要优化，这里FloydWarshall通过动态规划进行优化
*，并且使用邻接矩阵来表示图。
*d(i,j);ifm=0
*D(i,j,m)={
*min(D(i,m,m-1)+D(m,j,m-1),D(i,j,m-1));ifm!=0
*@authorminjun
*@date2015年6月1日上午9:39:42
*
*/
publicclassFloydWarshall{
privatedouble[][]d;
privateint[][]prev;
privateintv;
privatebooleannegativeCycle;
publicFloydWarshall(intv){
this.v=v;
d=newdouble[v][v];
prev=newint[v][v];
//默认设置所有节点都不可达，而自己到自己是可达并且距离为0.0
for(inti=0;ij路径中的一个中间点
for(inti=0;id[i][k]+d[k][j]){
d[i][j]=d[i][k]+d[k][j];
prev[i][j]=k;
}
}
}
}
//四舍五入距离
for(inti=0;ii的距离d[i][i]，如果存在小于0的，表示这个i->i的环路的权重和形成了一个负值，也就是存在这个负权重
//在之前的其他最短路径算法中，无法通过这个方法来检测负环，因为之前路径距离都是保存在一个一维数组中，相等于只能检测d[0][0]，无法检测每个d[i][i]
for(inti=0;ib最短路径的距离
*@param@parama
*@param@paramb
*@param@return设定文件
*@returndouble返回类型
*@throws
*/
publicdoubledistTo(inta,intb){
if(hasNegativeCycle())
thrownewRuntimeException("有负权重环，不存在最短路径");
returnd[a][b];
}
/**
*
*@Title:printShortestPath
*@Description:打印a->b最短路径
*@param@return设定文件
*@returnIterable返回类型
*@throws
*/
publicbooleanprintShortestPath(inta,intb){
if(hasNegativeCycle()){
System.out.print("有负权重环，不存在最短路径");
}elseif(a==b)
System.out.println(a+"->"+b);
else{
System.out.print(a+"->");
path(a,b);
System.out.print(b);
}
returntrue;
}
privatevoidpath(inta,intb){
intk=prev[a][b];
if(k==-1){
return;
}
path(a,k);
System.out.print(k+"->");
path(k,b);
}
/**
*
*@Title:addEdge
*@Description:添加边
*@param@parama
*@param@paramb
*@param@paramw设定文件
*@returnvoid返回类型
*@throws
*/
publicvoidaddEdge(inta,intb,doublew){
d[a][b]=w;
}
publicstaticvoidmain(String[]args){
//不含负权重环的文本数据
Stringtext1="F:\\算法\\attach\\tinyEWDn.txt";
//含有负权重环的文本数据
Stringtext2="F:\\算法\\attach\\tinyEWDnc.txt";
Inin=newIn(text1);
intn=in.readInt();
FloydWarshallf=newFloydWarshall(n);
inte=in.readInt();
for(inti=0;i
如果采用负权重环图，则会抛出异常，提示负环并表示无最短路径
如果采用不含负环的图，则会打印如下内容（目前以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
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持!