BFSとダイクストラのアルゴリズムの違い
1. 概要
グラフ理論では、 SSSP(単一ソース最短経路)アルゴリズムが、開始ノード(ソース)からグラフ内の他のすべてのノードへの最短経路を見つける問題を解決します。 この定義に該当する主なアルゴリズムは、幅優先探索(BFS)およびダイクストラのアルゴリズムです。
このチュートリアルでは、両方のアルゴリズムの一般的な説明を示します。 また、それらの違いと、それぞれをいつ使用するかについても説明します。
2. 一般的なアルゴリズム
どちらのアルゴリズムも同じ一般的な考え方を持っています。 ソースノードから開始し、ノードごとにグラフを調べます。 各ステップでは、常にソースノードに最も近いノードに移動します。
一般的なアルゴリズムをよりよく説明するフローチャートを見てみましょう。
ご覧のとおり、最初の2つの手順は、距離を大きな値で初期化し、ソースノードをキューに追加することです。 次に、キューが空になるまで反復を実行します。 各反復で、ソースノードからの距離が最も短いノードをキューから抽出します。
その後、抽出されたノードのすべてのネイバーを訪問し、達成できた新しい距離を確認します。 新しい距離が古い距離よりも優れている場合は、このノードの距離を更新してキューにプッシュします。 最後に、アルゴリズムは、キューが空になるまでもう1回反復を実行するように移動します。
アルゴリズムが終了すると、グラフ内のソースノードから他のすべてのノードへの最短パスが得られます。
ただし、グラフは加重または非加重のいずれかであるため、両方の場合にまったく同じアルゴリズムを使用することはできません。 したがって、2つのアルゴリズムがあります。 BFSは、重み付けされていないグラフの最短経路を計算します。 一方、ダイクストラのアルゴリズムは、重み付きグラフで同じことを計算します。
3. BFSアルゴリズム
重み付けされていないグラフを処理するときは、訪問するエッジの数を減らすことに常に注意を払っています。 したがって、ソースノードのすべての直接隣接ノードの距離は1に等しいと確信しています。 次に確信できるのは、ソースノードのすべての2番目の隣接ノードの距離が2に等しいということです。
このアイデアは、グラフのすべてのノードをカバーするまで有効です。
すべてのエッジが同じ重みを持つ重み付きグラフでは、BFSアルゴリズムが最短経路を正しく計算することに注意してください。 その理由は、訪問するエッジの数を減らすことに関心があるためです。これは、すべてのエッジの重みが等しい場合に当てはまります。
一般的なアルゴリズムに対して実行する必要のある更新について考えてみましょう。 私たちが従う主なアプローチは、常に以前に到達したノードから開始することです。 これは、単純なキューにあるFIFO(先入れ先出し)の概念に似ています。 したがって、BFSでは単純なキューを使用します。 一般的なアルゴリズムに対して行う必要のある更新はこれ以上ないことがわかります。
通常のキューを使用しているため、プッシュ操作とポップ操作には時間がかかります。 したがって、合計時間計算量はです。ここで、は頂点の数であり、はグラフのエッジの数です。
4. ダイクストラのアルゴリズム
加重グラフに関しては、隣接ノードが常に最短経路を持っている必要はありません。 ただし、エッジが最も短いネイバーには、より短いパスで到達できません。 その理由は、他のすべてのエッジの重みが大きいため、それらを単独で通過すると距離が長くなるためです。
ダイクストラのアルゴリズムは、このアイデアを使用して貪欲なアプローチを考え出します。 各ステップで、最短パスのノードを選択します。 このコストを修正し、このノードのネイバーをキューに追加します。 したがって、キューは最小のコストに基づいてキュー内のノードを並べ替えることができなければなりません。 これを実現するために、優先キューの使用を検討できます。
まだ1つの問題があります。 重み付けされていないグラフでは、別のパスからノードに到達したときに、最初は最短パスを持つ必要があると確信していました。 加重グラフでは、それが常に正しいとは限りません。 より短いパスでノードに到達した場合は、その距離を更新してキューに追加する必要があります。 これは、同じノードが複数回追加される可能性があることを意味します。
したがって、抽出されたノードのコストを実際に保存されたコストと常に比較する必要があります。 抽出された距離が保存された距離よりも大きい場合は、このノードが早い段階で追加されたことを意味します。 後で、より短いパスを見つけて更新したに違いありません。 また、ノードをキューに再度追加したため、この抽出は安全に無視できます。
各ノードのネイバーに1回だけアクセスしているため、エッジにも1回だけアクセスしています。 また、プッシュおよびポップ操作に時間計算量のある優先キューを使用できます。 したがって、合計時間計算量はです。
5. 例
次のグラフを見てください。 これには、BFSアルゴリズムを単純な重み付けされていないグラフに適用する例が含まれています。 文字はノードインデックスに対応し、数字はBFSアルゴリズムを実行した後に保存された距離を示します。
アルゴリズムがレベルごとにノードを訪問していることがはっきりとわかります。 まず、すべての隣人がレベル1で訪問されます。 次に、すべての2番目のネイバーがレベル2で訪問され、以下同様に続きます。 その結果、ソースノードから始まるすべてのノードへの最短経路を計算することができます。
それでは、ダイクストラのアルゴリズムを同じグラフの加重バージョンに適用した結果を見てみましょう。
ノードはソースから1ステップ離れていますが、エッジのコストが最も低いため、ダイクストラのアルゴリズムは最初にノードを探索しました。
次に、から、ノードへの短いパスが見つかりました。これは、アルゴリズムが保存したパスです。
から一歩離れていますが、直接訪問しなかったことにも注意してください。 その理由は、との間のエッジには非常に大きなコストがかかるためです。 幸いなことに、私たちは直接の端よりも短い道から到達することができました。
6. 比較
次の表は、2つのアルゴリズムの比較をまとめたものです。
7. 結論
このチュートリアルでは、BFSの一般的なアルゴリズムとダイクストラのアルゴリズムを紹介しました。 次に、2つのアルゴリズムの主な類似点と相違点について説明しました。
その後、同じグラフの重み付けされていないバージョンと重み付けされたバージョンの両方に両方のアルゴリズムを適用した結果を確認しました。
最後に、両方のアルゴリズムを比較しました。