1

ダイクストラのアルゴリズムは、開始点からの距離によって順序付けられる優先キューを使用しますが、頂点の距離はアルゴリズム中に変化します。プライオリティ キュー自体がいつ並べ替えられるかはわかりませんが、次のコンパレータがある場合:

struct compareByDistance
{
bool operator()(Vertex const &a, Vertex const &b)
    {
        return( getDistance(a) < getDistance(b) );
    }  
};

アルゴリズムの間、キューから値を削除するだけなので、それ自体が完全に並べ替えられるとは想像できません。したがって、距離の値が変更された場合、キューは距離の順序にはなりません。

これと同様にどのように実装しますか？

4

2 に答える 2

0

Google の min-max (通常はデフォルト) ヒープ。優先キューとして機能します。要素を常に一番上にポップする場所。これは、距離が最も小さいノードになります。

于 2013-03-07T13:16:40.383 に答える
0

考えられる解決策の 1 つは、最小距離が見つかったすべてのノードを追跡する訪問済み配列を持つことです (つまり、一度キューからポップアウトされています)。アイテムをキューからポップするたびに、訪問した配列をチェックして、ノードの最短距離が見つかったかどうかを確認します。その場合は、その要素を無視します。コードは次のようになります:-

while(!queue.empty())
{
node n1= queue.top();
queue.pop();
if(visited[n1]) continue;

////
//Rest of the code here
////
}

注:これは最適なソリューションではない可能性があります。

于 2013-05-11T05:56:57.413 に答える