我正在尝试使用 dijktra 算法打印特定邻接矩阵的最短路径。我的 dijkstra 算法运行良好，我得到了正确的距离。但是，当打印出路径时，我得到的路径不正确。这是我用于打印路径的代码:
我的第一类是接收邻接矩阵的驱动程序。该矩阵包含文件顶部的大小、中间的实际矩阵以及文件末尾的源顶点。这一切都可以很好地计算最短距离。以下是我的完整代码。
public void findPath(int size, int s) {
// print the path and the distance of each vertex
int j;
// iterate to find the distances
for (int i = 0; i < size; i++) {
System.out.print("[" + distance[i] + "] ");
if (i != 0) {
System.out.print(s);
j = i;
do {
j = path[j];
System.out.print(" <- " + j);
} while (j != startVertex);
}
System.out.println();
}
}
}
最佳答案
您的 findPath 方法存在以下问题:
- 您使用
if (i != 0)行无缘无故地跳过输出。 - 您的数据采用从 0 开始的索引形式，而您所需的输出是从 1 开始，并且您没有在它们之间进行转换。
- 您正在以与您想要的相反的顺序输出数据，当您的预期输出将起点放在最后时，首先打印路径的起点。
- 通过在打印任何内容之前执行路径中的一个步骤，您将跳过路径的第一步。
- 通过使用
do循环而不是while，您将打印短路径的虚假“静止移动”路径步骤。
我没有太多检查你的 dijkstra 逻辑，但这些错误的组合会将与你的预期输出匹配的路径数据转换为观察到的输出，所以我认为你是正确的，dijkstra 算法工作正常。
修复其中大部分应该是微不足道的，但修复错误 #3 将需要对算法进行较小的更改 - 在输出任何路径之前跟踪并反转路径。
为了更清楚起见，这是您的原始代码，其中标记了所有修复点:
public void findPath(int size, int s) {
// print the path and the distance of each vertex
int j;
// iterate to find the distances
for (int i = 0; i < size; i++) {
System.out.print("[" + distance[i] + "] ");
// FIX #1: Remove this if statement
if (i != 0) {
System.out.print(s);
j = i;
// FIX #5: Use while instead of do
do {
// FIX #4: swap the order of these two lines
j = path[j];
// FIX #2: print j+1, not j
// FIX #3: Instead of print, push onto a stack
System.out.print(" <- " + j);
} while (j != startVertex);
// FIX #3: Put your pop-and-print loop here. It should not
// involve i, and should end when the stack is empty, not
// any other condition.
}
System.out.println();
}
}
}
关于java - 最短路径 Dijkstra Java，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35733833/