学习资料
迪杰斯特拉计算的是单源最短路径,而弗洛伊德计算的是多源最短路径
代码
public class Main {
//不能设置为Integer.MAX_VALUE,否则两个Integer.MAX_VALUE相加会溢出导致出现负权
public static int MaxValue = 10000;
public static int[][] path;
public static void main(String[] args) {
//创建顶点和边
char[] data = {'A','B','C','D','E','F','G'};
int[][] matrix = {
{10000,5,7,10000,10000,10000,2},
{5,10000,10000,9,10000, 10000,3},
{7,10000,10000,10000,8,10000,10000},
{10000,9,10000,10000,10000,4,10000},
{10000,10000,8,10006,10000,5,4},
{10000,10000,10000,4,5,10000,6},
{2,3,10000,10000,4,6,10000}};
//初始化路径数组
path = new int[matrix.length][matrix.length];
floyd(matrix);
}
//非递归实现
public static void floyd(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
path[i][j] = -1;
}
}
for (int m = 0; m < matrix.length; m++) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
if (matrix[i][m] + matrix[m][j] < matrix[i][j]) {
matrix[i][j] = matrix[i][m] + matrix[m][j];
//记录经由哪个点到达
path[i][j] = m;
}
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
if (i != j) {
if (matrix[i][j] == MaxValue) {
System.out.println(i + "到" + j + "不可达");
} else {
System.out.print(i + "到" + j + "的最短路径长度是:" + matrix[i][j]);
System.out.print("最短路径为:" + i + "->");
findPath(i, j);
System.out.println(j);
}
}
}
}
}
//递归寻找路径
public static void findPath(int i, int j) {
int m = path[i][j];
if (m == -1) {
return;
}
findPath(i, m);
System.out.print(m + "->");
findPath(m, j);
}
}
结果
0到1的最短路径长度是:5最短路径为:0->1
0到2的最短路径长度是:7最短路径为:0->2
0到3的最短路径长度是:12最短路径为:0->6->5->3
0到4的最短路径长度是:6最短路径为:0->6->4
0到5的最短路径长度是:8最短路径为:0->6->5
0到6的最短路径长度是:2最短路径为:0->6
1到0的最短路径长度是:5最短路径为:1->0
1到2的最短路径长度是:12最短路径为:1->0->2
1到3的最短路径长度是:9最短路径为:1->3
1到4的最短路径长度是:7最短路径为:1->6->4
1到5的最短路径长度是:9最短路径为:1->6->5
1到6的最短路径长度是:3最短路径为:1->6
2到0的最短路径长度是:7最短路径为:2->0
2到1的最短路径长度是:12最短路径为:2->0->1
2到3的最短路径长度是:17最短路径为:2->4->5->3
2到4的最短路径长度是:8最短路径为:2->4
2到5的最短路径长度是:13最短路径为:2->4->5
2到6的最短路径长度是:9最短路径为:2->0->6
3到0的最短路径长度是:12最短路径为:3->5->6->0
3到1的最短路径长度是:9最短路径为:3->1
3到2的最短路径长度是:17最短路径为:3->5->4->2
3到4的最短路径长度是:9最短路径为:3->5->4
3到5的最短路径长度是:4最短路径为:3->5
3到6的最短路径长度是:10最短路径为:3->5->6
4到0的最短路径长度是:6最短路径为:4->6->0
4到1的最短路径长度是:7最短路径为:4->6->1
4到2的最短路径长度是:8最短路径为:4->2
4到3的最短路径长度是:9最短路径为:4->5->3
4到5的最短路径长度是:5最短路径为:4->5
4到6的最短路径长度是:4最短路径为:4->6
5到0的最短路径长度是:8最短路径为:5->6->0
5到1的最短路径长度是:9最短路径为:5->6->1
5到2的最短路径长度是:13最短路径为:5->4->2
5到3的最短路径长度是:4最短路径为:5->3
5到4的最短路径长度是:5最短路径为:5->4
5到6的最短路径长度是:6最短路径为:5->6
6到0的最短路径长度是:2最短路径为:6->0
6到1的最短路径长度是:3最短路径为:6->1
6到2的最短路径长度是:9最短路径为:6->0->2
6到3的最短路径长度是:10最短路径为:6->5->3
6到4的最短路径长度是:4最短路径为:6->4
6到5的最短路径长度是:6最短路径为:6->5