Java Floyd算法求有权图（非负权）的最短路径并打印

Java Floyd算法求有权图（非负权）的最短路径并打印

状态转移方程：d(i,j) = min(d(i,j),d(i,k)+d(k,j))，其中i

思路对于每一个k(i

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];

}

}

}

}

pripddvRUaGvate 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));

shttp://b.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)已经为各自的最小值。网上关于这个的证明文章非常的少，如果有大佬有严谨的证明过程还望不吝赐教。

思路对于每一个k(i

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];

}

}

}

}

pripddvRUaGvate 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));

shttp://b.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)已经为各自的最小值。网上关于这个的证明文章非常的少，如果有大佬有严谨的证明过程还望不吝赐教。

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];

}

}

}

}

pripddvRUaGvate 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));

shttp://b.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)已经为各自的最小值。网上关于这个的证明文章非常的少，如果有大佬有严谨的证明过程还望不吝赐教。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。