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

摘要: 算法导论之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

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

# 算法导论之FloydWarshall算法  # FloydWarshall算法  # Java算法之数组冒泡排序代码实例讲解  # Java算法之串的简单处理  # Java算法实现调整数组顺序使奇数位于偶数之前的讲解  # Java算法实现杨辉三角的讲解  # Java算法之冒泡排序实例代码  # Java算法之最长公共子序列问题(LCS)实例分析  # java算法实现红黑树完整代码示例  # Java算法之堆排序代码示例  # java算法之二分查找法的实例详解  # java算法实现预测双色球中奖号码  # Java算法之递归算法计算阶乘  # JAVA算法起步之插入排序实例  # JAVA算法起步之堆排序实例  # JAVA算法起步之快速排序实例  # 关于各种排列组合java算法实现方法  # Java算法之时间复杂度和空间复杂度的概念和计算  # 最短  # 两点  # 不存在  # 这种情况  # 可达  # 不含  # 以对  # 则会  # 图中  # 这样的话  # 都是  # 都不  # 形成了  # 希望能  # 很简单  # 在一  # 谢谢大家  # 方法来  # 抛出  # 更小 

相关文章： 上海制作企业网站有哪些,上海有哪些网站可以让企业免费发布招聘信息？  网站网页制作电话怎么打,怎样安装和使用钉钉软件免费打电话？  百度网页制作网站有哪些,谁能告诉我百度网站是怎么联系？    c# 在高并发场景下，委托和接口调用的性能对比  建站之星伪静态规则如何设置？  图册素材网站设计制作软件,图册的导出方式有几种？  简历在线制作网站免费版,如何创建个人简历？  武汉外贸网站制作公司,现在武汉外贸前景怎么样啊？  建站之星在线版空间：自助建站+智能模板一键生成方案  如何续费美橙建站之星域名及服务？  php条件判断怎么写_ifelse和switchcase的使用区别【对比】  如何通过云梦建站系统实现SEO快速优化？  小说建站VPS选用指南：性能对比、配置优化与建站方案解析  建站之星导航菜单设置与功能模块配置全攻略  公司门户网站制作流程,华为官网怎么做？  湖南网站制作公司,湖南上善若水科技有限公司做什么的？  如何用手机制作网站和网页,手机移动端的网站能制作成中英双语的吗？  网站好制作吗知乎,网站开发好学吗？有什么技巧？  广州网站建站公司选择指南：建站流程与SEO优化关键词解析  如何用狗爹虚拟主机快速搭建网站？  广州网站制作的公司,现在专门做网站的公司有没有哪几家是比较好的，性价比高，模板也多的？  公司网站制作费用多少,为公司建立一个网站需要哪些费用？  Python如何创建带属性的XML节点  如何用腾讯建站主机快速创建免费网站？  中山网站推广排名,中山信息港登录入口？  定制建站是什么？如何实现个性化需求？  广州网站设计制作一条龙,广州巨网网络科技有限公司是干什么的？  如何在香港免费服务器上快速搭建网站？  制作假网页,招聘网的薪资待遇，会有靠谱的吗？一面试又各种折扣？  如何快速生成橙子建站落地页链接？  南平网站制作公司,2025年南平市事业单位报名时间？  如何通过智能用户系统一键生成高效建站方案？  如何快速建站并高效导出源代码？  如何获取开源自助建站系统免费下载链接？  移动端手机网站制作软件,掌上时代，移动端网站的谷歌SEO该如何做？  如何在万网开始建站？分步指南解析  C++中引用和指针有什么区别？（代码说明）  制作国外网站的软件,国外有哪些比较优质的网站推荐？  如何快速搭建FTP站点实现文件共享？  如何通过VPS搭建网站快速盈利？  如何基于云服务器快速搭建个人网站？  如何在Golang中使用encoding/gob序列化对象_存储和传输数据  建站之星如何配置系统实现高效建站？  如何快速搭建虚拟主机网站？新手必看指南  linux top下的 minerd 木马清除方法  如何快速搭建自助建站会员专属系统？  建站之星后台密码如何安全设置与找回？  建站主机如何选？高性价比方案全解析  公司门户网站制作公司有哪些,怎样使用wordpress制作一个企业网站？