英文:
I need help implement all pair shortest path algorithm into a code given
问题
这里是您要翻译的内容：
我希望有人能够帮忙将以下算法实现到以下的Java代码中，我也会添加图表和示例输出。
[Java代码，抱歉不让我发布][https://i.stack.imgur.com/meipB.png]
[算法][https://i.stack.imgur.com/pE6Pv.png]
[图表][https://i.stack.imgur.com/WnSFk.png]
[输出][https://i.stack.imgur.com/Mpdoz.png]
[输出][https://i.stack.imgur.com/geBJP.png]
英文:
I would really if someone could help implements the following algorithm into the following java code, ill also add the graph and sample output.
[Java code sorry it wouldn't let me post][https://i.stack.imgur.com/meipB.png]
[Algorithm}[https://i.stack.imgur.com/pE6Pv.png]
[Graph][https://i.stack.imgur.com/WnSFk.png]
[Output][https://i.stack.imgur.com/Mpdoz.png]
[Output][https://i.stack.imgur.com/geBJP.png]
答案1
得分: 0
以下是翻译好的代码部分：
public class Graph {
public static void main(String[] args) {
int[][] W = new int[][] { { 0, 2, Integer.MAX_VALUE, 2 }, { 0, 0, Integer.MAX_VALUE, 2 },
{ 1, -1, 0, Integer.MAX_VALUE }, { Integer.MAX_VALUE, -1, -1, 0 } };
int[][] result = APSP1(W);
display(4, result);
}
private static int[][] APSP1(int[][] w) {
int n = w.length;
LinkedList<int[][]> L = new LinkedList<int[][]>();
L.add(w.clone());
for (int i = 1; i < n - 1; i++) {
display(i, L.get(i-1));
L.add(Extend(L.get(i - 1), w));
}
return L.get(n - 2);
}
private static void display(int i, int[][] arr) {
System.out.println("L" + i);
for (int[] ar : arr) {
for (int a : ar) {
if (a == Integer.MAX_VALUE) {
System.out.print(" ~ ");
} else {
System.out.print(" " + a + " ");
}
}
System.out.println();
}
System.out.println();
}
private static int[][] Extend(int[][] l, int[][] w) {
int n = l.length;
int[][] l$ = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
l$[i][j] = Integer.MAX_VALUE;
for (int k = 0; k < n; k++) {
int n2;
if (l[i][k] == Integer.MAX_VALUE || w[k][j] == Integer.MAX_VALUE) {
n2 = Integer.MAX_VALUE;
} else {
n2 = l[i][k] + w[k][j];
}
l$[i][j] = min(l[i][j], n2);
}
}
}
return l$;
}
private static int min(int n1, int n2) {
if (n1 == Integer.MAX_VALUE && n2 == Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (n1 >= Integer.MAX_VALUE) {
return n2;
}
if (n2 >= Integer.MAX_VALUE) {
return n1;
}
return n1 < n2 ? n1 : n2;
}
}
在你的 GeBJP 图像中，最短路径从 A 到 C 显示为 ABDC，总成本为 3，但在图中，A->(2)->D->(-1)->C 是最短路径，成本为 1。
英文:
Here I have posted implemented algorithm it seems it is not giving correct L[ ] values which are required for printing vertices. Please once have look is algorithm is correct or not before that i cant proceed.
public class Graph {
public static void main(String[] args) {
int[][] W = new int[][] { { 0, 2, Integer.MAX_VALUE, 2 }, { 0, 0, Integer.MAX_VALUE, 2 },
{ 1, -1, 0, Integer.MAX_VALUE }, { Integer.MAX_VALUE, -1, -1, 0 } };
int[][] result = APSP1(W);
display(4, result);
}
/**
* @param w
* @return
*/
private static int[][] APSP1(int[][] w) {
int n = w.length;
LinkedList<int[][]> L = new LinkedList<int[][]>();
L.add(w.clone());
// display(1, L.get(0));
for (int i = 1; i < n - 1; i++) {
display(i, L.get(i-1));
L.add(Extend(L.get(i - 1), w));
}
return L.get(n - 2);
}
/**
* @param i
* @param integers
*/
private static void display(int i, int[][] arr) {
System.out.println("L" + i);
for (int[] ar : arr) {
for (int a : ar) {
if (a == Integer.MAX_VALUE) {
System.out.print(" ~ ");
} else {
System.out.print(" " + a + " ");
}
}
System.out.println();
}
System.out.println();
}
/**
* @param integers
* @param w
* @return
*/
private static int[][] Extend(int[][] l, int[][] w) {
int n = l.length;
int[][] l$ = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
l$[i][j] = Integer.MAX_VALUE;
for (int k = 0; k < n; k++) {
int n2;
if (l[i][k] == Integer.MAX_VALUE || w[k][j] == Integer.MAX_VALUE) {
n2 = Integer.MAX_VALUE;
} else {
n2 = l[i][k] + w[k][j];
}
l$[i][j] = min(l[i][j], n2);
}
}
}
return l$;
}
/**
* @param integer
* @param i
* @return
*/
private static int min(int n1, int n2) {
if (n1== Integer.MAX_VALUE && n2 == Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (n1 >= Integer.MAX_VALUE) {
return n2;
}
if (n2 >= Integer.MAX_VALUE) {
return n1;
}
return n1 < n2 ? n1 : n2;
}
}
In your geBJP image showing ABDC as shortest path[from A -> C] A->(2)->B->(2)->D->(-1)->C total cost = 3 but in graph A->(2)->D->(-1)->C is shortest path with cost = 1
专注分享java语言的经验与见解，让所有开发者获益！
评论