1

ダイクストラ アルゴリズムには、「最短パスのノードを選択する」というステップがあります。このステップが であることを認識していunnecessary if we dont throw a node out of the graph/queueます。これは私の知る限りではうまく機能し、既知の欠点はありません。これがコードです。失敗したら教えてください。もしそうなら、どうやって？[編集 => このコードはテスト済みで、うまく機能しますが、私のテストケースが完全ではなかった可能性があるため、スタックオーバーフローに投稿しています]

  public Map<Integer, Integer> findShortest(int source) {
        final Map<Integer, Integer> vertexMinDistance = new HashMap<Integer, Integer>();
        final Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(source);
        vertexMinDistance.put(source, 0);

        while (!queue.isEmpty()) {
            source = queue.poll();
            List<Edge> adjlist = graph.getAdj(source);
            int sourceDistance = vertexMinDistance.get(source);

            for (Edge edge : adjlist) {
                int adjVertex = edge.getVertex();
                if (vertexMinDistance.containsKey(adjVertex)) {
                    int vertexDistance = vertexMinDistance.get(adjVertex);
                    if (vertexDistance > (sourceDistance + edge.getDistance())) {
                         //previous bug
                         //vertexMinDistance.put(adjVertex, vertexDistance);
                         vertexMinDistance.put(adjVertex, sourceDistance + edge.getDistance())
                    }
                } else {
                    queue.add(adjVertex);
                    vertexMinDistance.put(adjVertex, edge.getDistance());
                }   
            }
        }
        return vertexMinDistance;
    }
4

1 に答える 1

1

問題1

コードに次のようなバグがあると思います。

                int vertexDistance = vertexMinDistance.get(adjVertex);
                if (vertexDistance > (sourceDistance + edge.getDistance())) {
                    vertexMinDistance.put(adjVertex, vertexDistance);
                }

これは効果がないためです (adjVertex の vertexMinDistance は元の値に戻されます)。

より良いのは次のようなものです：

                int vertexDistance = vertexMinDistance.get(adjVertex);
                int newDistance = sourceDistance + edge.getDistance();
                if (vertexDistance > newDistance ) {
                    vertexMinDistance.put(adjVertex, newDistance );
                }

問題 2

次のようなものを使用して、adjVertex をキューに追加する必要もあります。

                int vertexDistance = vertexMinDistance.get(adjVertex);
                int newDistance = sourceDistance + edge.getDistance();
                if (vertexDistance > newDistance ) {
                    vertexMinDistance.put(adjVertex, newDistance );
                    queue.add(adjVertex);
                }

これを行わないと、次のようなグラフに対して間違った答えが得られます。

A->B (1)
A->C (10)
B->C (1)
B->D (10)
C->D (1)

正しいパスは、重み 3 の A->B->C->D ですが、変更がなければ、アルゴリズムはより長いパスを選択すると思います (C への短いパスが見つかったら、C を再検査しないため)。 .

ハイレベルなレスポンス

これらの変更により、このアプローチは基本的に健全だと思いますが、計算の複雑さに注意する必要があります。

Dijkstra は、メイン ループを V 回 (V はグラフ内の頂点の数) 回すだけで済みますが、アルゴリズムによっては、特定のグラフに対してさらに多くのループが必要になる場合があります。

正しい答えが得られますが、時間がかかる場合があります。

最悪の場合の複雑さは Dijkstra よりもはるかに悪くなりますが、実際にどれだけうまく機能するかに興味があります。私の推測では、まばらなほぼ木のようなグラフではうまく機能しますが、密集したグラフではうまく機能しません。

于 2013-10-05T20:40:19.227 に答える