BFSとダイクストラのアルゴリズムの違い

1. 概要

グラフ理論では、 SSSP（単一ソース最短経路）アルゴリズムが、開始ノード（ソース）からグラフ内の他のすべてのノードへの最短経路を見つける問題を解決します。この定義に該当する主なアルゴリズムは、幅優先探索（BFS）およびダイクストラのアルゴリズムです。

このチュートリアルでは、両方のアルゴリズムの一般的な説明を示します。また、それらの違いと、それぞれをいつ使用するかについても説明します。

2. 一般的なアルゴリズム

どちらのアルゴリズムも同じ一般的な考え方を持っています。ソースノードから開始し、ノードごとにグラフを調べます。各ステップでは、常にソースノードに最も近いノードに移動します。

一般的なアルゴリズムをよりよく説明するフローチャートを見てみましょう。

ご覧のとおり、最初の2つの手順は、距離を大きな値で初期化し、ソースノードをキューに追加することです。次に、キューが空になるまで反復を実行します。各反復で、ソースノードからの距離が最も短いノードをキューから抽出します。

その後、抽出されたノードのすべてのネイバーを訪問し、達成できた新しい距離を確認します。新しい距離が古い距離よりも優れている場合は、このノードの距離を更新してキューにプッシュします。最後に、アルゴリズムは、キューが空になるまでもう1回反復を実行するように移動します。

アルゴリズムが終了すると、グラフ内のソースノードから他のすべてのノードへの最短パスが得られます。

ただし、グラフは加重または非加重のいずれかであるため、両方の場合にまったく同じアルゴリズムを使用することはできません。したがって、2つのアルゴリズムがあります。 BFSは、重み付けされていないグラフの最短経路を計算します。一方、ダイクストラのアルゴリズムは、重み付きグラフで同じことを計算します。

3. BFSアルゴリズム

重み付けされていないグラフを処理するときは、訪問するエッジの数を減らすことに常に注意を払っています。したがって、ソースノードのすべての直接隣接ノードの距離は1に等しいと確信しています。次に確信できるのは、ソースノードのすべての2番目の隣接ノードの距離が2に等しいということです。

このアイデアは、グラフのすべてのノードをカバーするまで有効です。唯一の例外は、以前にアクセスしたことがあるノードに到達した場合です。この場合、無視する必要があります。その理由は、以前はもっと短いパスで到達したに違いないからです。

すべてのエッジが同じ重みを持つ重み付きグラフでは、BFSアルゴリズムが最短経路を正しく計算することに注意してください。その理由は、訪問するエッジの数を減らすことに関心があるためです。これは、すべてのエッジの重みが等しい場合に当てはまります。

一般的なアルゴリズムに対して実行する必要のある更新について考えてみましょう。 私たちが従う主なアプローチは、常に以前に到達したノードから開始することです。これは、単純なキューにあるFIFO（先入れ先出し）の概念に似ています。したがって、BFSでは単純なキューを使用します。一般的なアルゴリズムに対して行う必要のある更新はこれ以上ないことがわかります。

通常のキューを使用しているため、プッシュ操作とポップ操作には時間がかかります。したがって、合計時間計算量はです。ここで、は頂点の数であり、はグラフのエッジの数です。

4. ダイクストラのアルゴリズム

加重グラフに関しては、隣接ノードが常に最短経路を持っている必要はありません。ただし、エッジが最も短いネイバーには、より短いパスで到達できません。その理由は、他のすべてのエッジの重みが大きいため、それらを単独で通過すると距離が長くなるためです。

ダイクストラのアルゴリズムは、このアイデアを使用して貪欲なアプローチを考え出します。 各ステップで、最短パスのノードを選択します。このコストを修正し、このノードのネイバーをキューに追加します。したがって、キューは最小のコストに基づいてキュー内のノードを並べ替えることができなければなりません。これを実現するために、優先キューの使用を検討できます。

まだ1つの問題があります。重み付けされていないグラフでは、別のパスからノードに到達したときに、最初は最短パスを持つ必要があると確信していました。加重グラフでは、それが常に正しいとは限りません。より短いパスでノードに到達した場合は、その距離を更新してキューに追加する必要があります。 これは、同じノードが複数回追加される可能性があることを意味します。

したがって、抽出されたノードのコストを実際に保存されたコストと常に比較する必要があります。抽出された距離が保存された距離よりも大きい場合は、このノードが早い段階で追加されたことを意味します。後で、より短いパスを見つけて更新したに違いありません。 また、ノードをキューに再度追加したため、この抽出は安全に無視できます。

各ノードのネイバーに1回だけアクセスしているため、エッジにも1回だけアクセスしています。また、プッシュおよびポップ操作に時間計算量のある優先キューを使用できます。したがって、合計時間計算量はです。