gpt4 book ai didi

java - 无需递归的 Floyd-Warshall 路径重建

转载 作者:塔克拉玛干 更新时间:2023-11-02 20:23:02 25 4
gpt4 key购买 nike

我正在使用来自 here 的 Floyd-Warshall 算法.

import static java.lang.String.format;
import java.util.Arrays;



public class FloydWarshall {


public static void main(String[] args) {
int[][] weights = {{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}};
int numVertices = 4;

floydWarshall(weights, numVertices);
}

static void floydWarshall(int[][] weights, int numVertices) {

double[][] dist = new double[numVertices][numVertices];
for (double[] row : dist)
Arrays.fill(row, Double.POSITIVE_INFINITY);

for (int[] w : weights)
dist[w[0] - 1][w[1] - 1] = w[2];

int[][] next = new int[numVertices][numVertices];
for (int i = 0; i < next.length; i++) {
for (int j = 0; j < next.length; j++)
if (i != j)
next[i][j] = j + 1;
}

for (int k = 0; k < numVertices; k++)
for (int i = 0; i < numVertices; i++)
for (int j = 0; j < numVertices; j++)
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = next[i][k];
}

printResult(dist, next);
}

static void printResult(double[][] dist, int[][] next) {
System.out.println("pair dist path");
for (int i = 0; i < next.length; i++) {
for (int j = 0; j < next.length; j++) {
if (i != j) {
int u = i + 1;
int v = j + 1;
String path = format("%d -> %d %2d %s", u, v,
(int) dist[i][j], u);
do {
u = next[u - 1][v - 1];
path += " -> " + u;
} while (u != v);
System.out.println(path);
}
}
}
}
}

算法本身很清楚,但我不明白的是 next 矩阵。根据我对 i,j 索引的理解,索引应该是从节点 i 到节点 j 的路径上的最后一个节点。然后递归地打印打印路径。但是这段代码在打印语句 printResult 中使用了某种不同的方法。所以我的问题是矩阵 next 到底是什么以及打印是如何工作的?

最佳答案

dist[i][j] = dist[i][k] + dist[k][j]说:当从 i 到 j 时,经过 k,取从 i 到 k 的最短路径,然后是从 k 到 j 的最短路径。这里:next[i][j] = next[i][k]它说当从 i 到 j 时,如果你从 i 到 k,首先去你想去的地方。

因此,u = next[u - 1][v - 1]; 行说:你现在是从你到 v 的路径上的下一个节点。

关于java - 无需递归的 Floyd-Warshall 路径重建,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50518175/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com