最短路径Dijkstra Java [英] Shortest Path Dijkstra Java

问题描述

我正在尝试使用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方法中存在以下问题:

1. 您正在使用if (i != 0)行无缘无故地跳过输出.
2. 您的数据采用基于0的索引的形式，所需的输出基于1的索引，并且您无需在它们之间进行转换.
3. 您将按照所需的相反顺序输出数据，当预期的输出将起点放在最后时，先打印路径的起点.
4. 通过在打印任何内容之前在路径中走一步，您将跳过路径的第一步.
5. 通过使用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();

        }
    }
}

I am trying to print the shortest path for a specific adjacency matrix using dijktra's algorithm. My dijkstra algorithm works fine, I am getting the correct distances. However when printing out the path I am getting an incorrect path. Here is my code for printing the path:

My first class is my driver that takes in an adjacency matrix. The matrix contains the size at the top of the file, the actual matrix in the middle, and the source vertex at the end of the file. That all works fine for calculating the shortest distance. The following is my full code.

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

    }

}
}

解决方案

You have the following problems in your findPath method:

1. You are skipping output for no reason with the if (i != 0) line.
2. Your data is in the form of 0-based indices, and your desired output is 1-based, and you aren't converting between them.
3. You are outputting data in the opposite order of what you want, printing the path's starting point first when your expected output puts the starting point last.
4. By following one step in the path before printing anything, you are skipping the path's first step.
5. By using a do loop instead of while, you are printing spurious "move by standing still" path steps for short paths.

I haven't examined your dijkstra logic much, but these errors in combination would transform path data that matches your expected output into the observed output, so I think you're correct that the dijkstra algorithm is working properly.

Fixing most of these should be trivial, but fixing error #3 will require a minor algorithmic change - trace and reverse the path before outputting any of it.

For greater clarity, here's your original code with all the fix points marked:

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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！