最短路径 Dijkstra Java

Question

我正在尝试使用 dijktra 算法打印特定邻接矩阵的最短路径。我的 dijkstra 算法运行良好，我得到了正确的距离。但是，当打印出路径时，我得到的路径不正确。这是我打印路径的代码：

我的第一个 class 是接受邻接矩阵的驱动程序。该矩阵包含文件顶部的大小、中间的实际矩阵和文件末尾的源顶点。这一切都适用于计算最短距离。以下是我的完整代码。

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

    }

}
}

Answer 1

您的 findPath 方法存在以下问题：

您无缘无故地跳过了 if (i != 0) 行的输出。
您的数据是从 0 开始的索引形式，而您想要的输出是从 1 开始的，并且您没有在它们之间进行转换。
您正在以与您想要的顺序相反的顺序输出数据，当您的预期输出将起点放在最后时，首先打印路径的起点。
在打印任何内容之前跟随路径中的一个步骤，您将跳过路径的第一步。
通过使用 do 循环而不是 while，您正在为短路径打印虚假的 "move by standing still" 路径步骤。

我没有过多检查您的 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();

        }
    }
}

最短路径 Dijkstra Java

Shortest Path Dijkstra Java

java

graph-theory

dijkstra

matrix