3

最初のノードと最後のノードの間の最短パスを取得しようとしています。問題は、私のコードが常に 0 を返すことです。これは、最初のノードと最初のノードの間の距離を計算しているためだと感じていますが、これはゼロになりますが、100% ではありません。コードが常に 0 を返すのはなぜですか?

adj 行列は [10][10] で、すべてのノードが接続されており、g.network[][] が行列です。

private static int dijkstras(Graph g) {
    // Dijkstra's Algorithm
    int[] best = new int[g.network.length];
    boolean[] visited = new boolean[g.network.length];
    int max = 10000; // Infinity equivalent.
    for (int i = 0; i < g.network.length; i++)
    {
        best[i] = max;
        visited[i] = false;
    }

    best[0] = 0;

    for(int i = 0; i < g.network.length; i++)
    {
        int min = max;
        int currentNode = 0;
        for (int j = 0; j < g.network.length; j++)
        {
            if (!visited[j] && best[j] < min)
            {
                currentNode = j;
                min = best[j];
            }
        }
        visited[currentNode] = true;
        for (int j = 0; j < g.network.length; j++)
        {
            if (g.network[currentNode][j] < max && best[currentNode] + g.network[currentNode][j] < best[j])
            {
                best[j] = best[currentNode] + g.network[currentNode][j];
            }
        }
    }
            return best[g.network.length - 2];
}
4

2 に答える 2

3

次のようにコードを変更することで、問題を解決した可能性があると思います（「0」でハードコードされた代わりに、開始点を渡しています）：

    private static int dijkstras(Graph g, int start) // Added a start point.
    {
    // Dijkstra's Algorithm
    int[] best = new int[g.network.length];
    boolean[] visited = new boolean[g.network.length];
    int max = 10000; // Infinity equivalent.
    for (int i = 0; i < g.network.length; i++)
    {
        best[i] = max;
        visited[i] = false;
    }

    best[start] = start; // Changed the 0 to variable start.

    for(int i = 0; i < g.network.length; i++)
    {
        int min = max;
        int currentNode = 0;
        for (int j = 0; j < g.network.length; j++)
        {
            if (!visited[j] && best[j] < min)
            {
                currentNode = j;
                min = best[j];
            }
        }
        visited[currentNode] = true;
        for (int j = 0; j < g.network.length; j++)
        {
            if (g.network[currentNode][j] < max && best[currentNode] +   g.network[currentNode][j] < best[j])
            {
                best[j] = best[currentNode] + g.network[currentNode][j];
            }
        }
    }
            return best[g.network.length - 2];
}

このコードを for ループで実行すると、ほら、ゼロだけが返されるわけではありません。

于 2012-05-03T23:11:53.223 に答える
1

私はあなたのコードを読みましたが、それが正しいダイクストラアルゴリズムであるとほぼ確信しているので、最初のノードと最後のノードの間にゼロパスがあると思います。

于 2012-05-03T02:56:17.087 に答える