16

私はダイクストラのアルゴリズムに取り組んでおり、1 つだけでなく、考えられる最短経路をすべて見つける必要があります。隣接行列を使用しており、ダイクストラのアルゴリズムを適用したところ、最短経路を見つけることができました。しかし、最小コストですべてのパスを見つける必要があります。つまり、可能なすべてのソリューションが存在する場合です。

これは、単一のソリューションに対して、私のアルゴリズムがどのように機能するかです。

public void dijkstra( int graph[][] )
{
    int d[] = new int[ graph.length ];
    int dC[] = new int[ graph.length ];
    int p[] = new int[ graph.length ];

    for( int i = 0; i < graph.length; i++ ){
        d[ i ] = 100; dC[ i ] = 100; p[ i ] = -1;
    }
    d[ 0 ] = 0; dC[ 0 ] = 0;

    int i = 0, min = 200, pos = 0; //You can change the min to 1000 to make it the largest number
    while( i < graph.length ){
        //extract minimum
        for( int j = 0; j < dC.length; j++ ){
            if( min > d[ j ] && dC[ j ] != -1 ){
                min = d[ j ]; pos = j;
            }
        }
        dC[ pos ] = -1;

        //relax
        for( int j = 0; j < graph.length; j++ ){
            if( d[ j ] > graph[ pos ][ j ] + d[ pos ] ){
                d[ j ] = graph[ pos ][ j ] + d[ pos ];
                p[ j ] = pos;
            }
        }
        i++; min = 200;
    }

    for( int j = 0; j < p.length; j++ ){
        System.out.print( p[ j ] + " " );
    }
    System.out.print( "\n" );
    for( int j = 0; j < d.length; j++ ){
        System.out.print( d[ j ] + " " );
    }
    System.out.print( "\n" );
}
4

8 に答える 8

16

Dijkstra のアルゴリズムを疑似コード形式で見ると、 Wikipedia Dijkstra's Algorithm Pseudocodeが表示されます。

リラックスと呼ばれるラインに気付くでしょう。現在、見つかったパスが現在の最短パスよりも小さい場合のみが含まれていますが、等しい場合は何も行われません。おそらく、すべての等しい短いパスをリストに保持する必要があります。

于 2010-05-12T13:59:40.250 に答える
4

ダイクストラのアルゴリズムの実装が優先キューに基づいている場合は、最初の解を取り、深さを記録し、距離が変わるまで解をポップアウトし続けます。

于 2010-05-12T13:57:48.163 に答える
3

グラフがエッジとweight = 0サイクルを許可する場合、無限に多くの最短パスがあり、それらすべてを出力することは期待できないことに注意してください!

重みがゼロのエッジがない場合、またはグラフが DAG の場合、ソリューションにはまだ問題があります。必要に応じてすべての最短パスが生成されないか、O(2^N)空間と時間の複雑さで生成されます。しかし、おそらく最短経路は同じ数だけ存在する可能性があるため、一般的なケースでより良い結果を期待することはできません。

これは、もう少し一般的な問題の最良の情報源です: k 最短経路の検索(Eppstein)。これを適用するには、最短パスを反復し、前のパスよりも長い最初のパスで停止します。

(同等の) 最短経路のみを見つけるという制限された問題については、上記の Anderson Imes のヒント (これは宿題ですか? そうでない場合は、誰かが説明する必要があります) が適切であり、上記よりもはるかに単純です。

于 2010-05-25T16:11:22.670 に答える
1

JgraphTの FloydWarshallShortestPaths クラスは、すべての最短パスを検出します。上記のコメントに基づいて、2 つの頂点間の最短経路を探しています。頂点から他のすべての頂点へのすべての最短パスを返すgetShortestPathsメソッドを使用することもできます。次に、興味のある結果をフィルタリングすることができます。

于 2015-08-19T23:15:29.077 に答える
1

Dijkstra のアルゴリズムを簡単に適用できるかどうかはよくわかりません。もちろん、訪問したエッジを削除するほど単純ではありません.n最短のものはそれらのいくつかを共有する可能性があるためです.

したがって、ほとんど力ずくであるがヒューリスティック指向の解決策は、これを試すことです。

  • 最短経路のすべてのエッジ E について:
    • E を削除し、新しいグラフに対して変更されたダイクストラを再度実行します
    • 最短経路が最初に取得した経路よりも長い場合は、停止します
    • それ以外の場合は、新しいサブグラフから一度に 1 つのエッジを削除することを再帰的に繰り返します

私の直感でnは、最初の解の長さ (エッジの数) に比例して複雑さが増し、うまくいくはずです... 最短経路がこれ以上ない場合、見つかった場合は最初のラウンドで終了するはずです別の、それはn-1試行を続けます。元のアルゴリズムに対する最悪の場合の複雑さの増加の見積もりは非常に悪いですが (n!私は推測しますか?)、それはまた多くのパスがあることを意味するので、それはどのアルゴリズムでも行う必要がある作業です...

編集:もう少し考えてみると、複雑さの増加は、最初に見つかったパスのノード数の階乗よりもさらに大きくなる可能性があります。2 番目のパスにはさらに多くのノードがある可能性があります! したがって、この方法の複雑さを見積もるのは非常に難しいと思いますが、有効な解の数にパス内のノードの平均数を掛けてノードの 2 乗を掛けたようなものになるはずです(この最後の項は、変更されていないアルゴリズム)。

編集 2:この主題に関する研究論文を見つけました。全文を入手するには購読が必要ですが、別の場所で見つけることができるかもしれません: http://ieeexplore.ieee.org/Xplore/login.jsp?reload=true&url =http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F7719%2F21161%2F00982778.pdf%3Farnumber%3D982778&authDecision=-201

于 2010-05-12T14:09:53.970 に答える
0

1982 年のこの論文では、すべての最短経路を与える、多次元の辺の重みを持つグラフのアルゴリズムについて説明しています。

アルゴリズムは単純な加重グラフでうまく機能するので、あなたの場合にはうまくいくはずです。

著者は、動作方法と実行時の複雑さの比較の両方で、Dijkstra と比較します。

疑似コードで、論文を言い換えると：

1. H is a heap of paths sorted on the weights of these paths, either
     a. lexicographically and decreasing in each element of the weight vector
     b. on the negative sum of all the elements in the weight vector
   Initially, H contains only path p0 (the starting point) the weight of which is O.
2. S1 through Sv are sets associated with vertices v1 through vv respectively.
   These sets contain the maximal paths to each vertex, as they are discovered.
   Initially, all sets are empty.
3. a. While (H is not empty) do begin
   b.   remove the root of H, p;
   c.   if p is not dominated by any of the paths in Sn where vn is last vertex of p
   d.     add it to Sn (the set of maxima for vertex vn)
   e.     for each possible extensions q of path p
   g.       if path q to node vm is not yet dominated by the maxima in Sm
   h.         insert q into H
于 2015-08-19T10:36:40.680 に答える