Java Floyd算法求有权图(非负权)的最短路径并打印
作者:花溪的小石头 时间:2023-04-10 12:53:42
状态转移方程:d(i,j) = min(d(i,j),d(i,k)+d(k,j)),其中i<k<j
思路对于每一个k(i<k<j),全部遍历下来之后,肯定会发生一次有效的比较
public class FloydTest {
private static int[][] matrix;
private static int[][] path;
public static void main(String[] args) {
initMatrixAndPath(
new int[][]{
{0, 1, 8, 5},
{1, 0, 7, 6},
{8, 7, 0, 2},
{5, 6, 2, 0}}
);
floyd(matrix, path);
printShortDistance();
printShortDistanceDetail();
}
private static void initMatrixAndPath(int[][] matrix) {
FloydTest.matrix = matrix;
FloydTest.path = new int[matrix.length][matrix.length];
for (int i = 0; i < FloydTest.matrix.length; i++) {
for (int j = 0; j < FloydTest.matrix[i].length; j++) {
path[i][j] = j;
}
}
}
private static void floyd(int[][] matrix, int[][] path) {
for (int k = 0; k < matrix.length; k++) {
for (int i = 0; i < matrix.length; i++)
for (int j = 0; j < matrix.length; j++) {
if (matrix[i][j] > matrix[i][k] + matrix[k][j]) {
matrix[i][j] = matrix[i][k] + matrix[k][j];
path[i][j] = path[i][k];
}
}
}
}
private static String getNodeName(int nodeIndex) {
return "v" + nodeIndex;
}
private static void printShortDistanceDetail() {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
int x = j;
StringBuilder sb = new StringBuilder("最短路径[v" + i + ",v" + j + "]为:");
sb.append(getNodeName(x));
sb.append("<--");
while (path[i][j] != x) {
x = path[i][x];
sb.append(getNodeName(path[i][x]));
sb.append("<--");
}
sb.append(getNodeName(i));
System.out.println(sb);
}
}
}
private static void printShortDistance() {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
System.out.println("v" + i + "到" + "v" + j + "最短路径为:" + matrix[i][j]);
}
}
}
}
输出结果
v0到v0最短路径为:0
v0到v1最短路径为:1
v0到v2最短路径为:7
v0到v3最短路径为:5
v1到v0最短路径为:1
v1到v1最短路径为:0
v1到v2最短路径为:7
v1到v3最短路径为:6
v2到v0最短路径为:7
v2到v1最短路径为:7
v2到v2最短路径为:0
v2到v3最短路径为:2
v3到v0最短路径为:5
v3到v1最短路径为:6
v3到v2最短路径为:2
v3到v3最短路径为:0
最短路径[v0,v0]为:v0<--v0
最短路径[v0,v1]为:v1<--v0
最短路径[v0,v2]为:v2<--v3<--v0
最短路径[v0,v3]为:v3<--v0
最短路径[v1,v0]为:v0<--v1
最短路径[v1,v1]为:v1<--v1
最短路径[v1,v2]为:v2<--v1
最短路径[v1,v3]为:v3<--v1
最短路径[v2,v0]为:v0<--v3<--v2
最短路径[v2,v1]为:v1<--v2
最短路径[v2,v2]为:v2<--v2
最短路径[v2,v3]为:v3<--v2
最短路径[v3,v0]为:v0<--v3
最短路径[v3,v1]为:v1<--v3
最短路径[v3,v2]为:v2<--v3
最短路径[v3,v3]为:v3<--v3
其他:看了网上的一些关于floyd算法证明的过程。其实最主要的一点,证明求d(i,k)+d(k,j)时,d(i,k)和d(k,j)已经为各自的最小值。网上关于这个的证明文章非常的少,如果有大佬有严谨的证明过程还望不吝赐教。
来源:https://segmentfault.com/a/1190000019763790
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
C#导出pdf的实现方法(浏览器不预览直接下载)
mybatis 实体类字段大小写问题 字段获取不到值的解决
![](https://img.aspxhome.com/file/2023/9/101989_0s.png)
分析讲解SpringMVC注解配置如何实现
Android自定义ViewGroup实现带箭头的圆角矩形菜单
![](https://img.aspxhome.com/file/2023/0/115990_0s.png)
C# ComboBox的联动操作(三层架构)
![](https://img.aspxhome.com/file/2023/5/113785_0s.png)
java IO流将一个文件拆分为多个子文件代码示例
![](https://img.aspxhome.com/file/2023/3/58193_0s.jpg)
C# BinaryReader实现读取二进制文件
![](https://img.aspxhome.com/file/2023/6/75626_0s.gif)
C#利用GDI+画图的基础实例教程
![](https://img.aspxhome.com/file/2023/1/82161_0s.png)
Java中四种访问权限资料整理
C# 读写XML(代码分享)
Java并发的CAS原理与ABA问题的讲解
![](https://img.aspxhome.com/file/2023/7/59987_0s.png)
利用C#版OpenCV实现圆心求取实例代码
![](https://img.aspxhome.com/file/2023/3/94663_0s.jpg)
c#实现简单控制台udp异步通信程序示例
教大家使用java实现顶一下踩一下功能
![](https://img.aspxhome.com/file/2023/2/92642_0s.jpg)
c#单例模式(Singleton)的6种实现
![](https://img.aspxhome.com/file/2023/7/89797_0s.gif)
关于Java的ArrayList数组自动扩容机制
Java8 使用 stream().sorted()对List集合进行排序的操作
![](https://img.aspxhome.com/file/2023/0/71930_0s.jpg)
IntelliJ IDEA 2020.1.2激活工具下载及破解方法免费可用至2089年(强烈推荐)
![](https://img.aspxhome.com/file/2023/1/92701_0s.jpg)