个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章java算法导论之FloydWarshall算法实现代码由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

摘要: 算法导论之FloydWarshall算法 。

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

?
1
2
3
4
5
6
FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径
 
     如果普通求最短路径，可以对图进行V次（顶点数）BellmanFord算法。 这样的话时间复杂度为EV^ 2
     如果是稀疏图，则近似于V^ 3
     但是如果是密集图，则时间复杂度会近似达到V^ 4 ，这种情况需要优化，这里FloydWarshall通过动态规划进行优化
     ，并且使用邻接矩阵来表示图。

实例代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
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作测试，其他点作为原点的最短路径可以自行尝试）:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

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

原文链接：https://my.oschina.net/u/1378920/blog/423862 。

最后此篇关于java算法导论之FloydWarshall算法实现代码的文章就讲到这里了,如果你想了解更多关于java算法导论之FloydWarshall算法实现代码的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

26 4 0
文章推荐： 使命召唤手游占点模式怎么玩 占点模式玩法技巧攻略
文章推荐： VBS教程：方法-GetBaseName 方法
文章推荐： VBS教程：方法-GetDrive 方法
文章推荐： VBS教程：方法-GetDriveName 方法
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com