ダイクストラのアルゴリズムは、実際にはフィボナッチヒープを使用して実装されていることを私は知っています。しかし、赤黒木を使用して実装しても、最悪の場合の実行時間がO（m log n）になる可能性はありますか？
質問する
1179 次
3 に答える
9
手始めに、フィボナッチヒープで実装されたダイクストラのアルゴリズムを実際に見ることはめったにありません。フィボナッチヒープは優れた漸近性能（O（m + n log n））を提供しますが、実際には、他のタイプのヒープがより効率的であるほど高い定数係数を持っています。
あなたの質問に関しては-はい、O（m log n）のパフォーマンスを得るための優先キューとして赤黒木を使用することができます。これが機能するのは、O（log n）時間で赤黒木から最小要素を見つけ、削除してから挿入することで、時間O（log n）でツリーのキー減少操作をシミュレートできるためです。ただし、赤黒木は参照の局所性が低く、メモリオーバーヘッドが大きいため、これはおそらく標準のバイナリヒープを使用するほど効率的ではありません。より一般的には、優先キューが必要なときはいつでも、バランスの取れた二分探索木を使用できますが、通常はやり過ぎです。
お役に立てれば！
于 2013-01-24T15:45:35.043 に答える
2
ダイクストラのアルゴリズムがフィボナッチヒープを使用して実装されているとは言えません。実際、Fiboncciはさまざまな操作に対して最も償却された複雑さを持っていますが、どのヒープでも問題ありません（これは非常に大きなグラフでしか表示されないことに注意してください）。ここでも赤黒木を使用すると、同じ計算の複雑さが達成されますが、赤黒木での作業がより複雑になるため、定数が高くなります。
このアルゴリズムに必要なのは、特定のセットから最小の要素を取得できるようにすることだけです。これがヒープの意味であり、この問題に最も適しています。赤黒木は他の多くのことを行うことができるため、この特定のケースではより複雑になり、プリフォームが悪化します。
于 2013-01-24T15:45:01.010 に答える
1
これは興味深い質問です。はい、赤黒木を使用して実装できます。以下に例を示します。
于 2018-05-22T19:13:28.000 に答える