Dijkstraのアルゴリズムを無向グラフに変更する

Question

質問：重み付けされた無向グラフのSSSP問題を解くためのDijkstraのアルゴリズムを適応させます。 グラフ。

アルゴリズムを変更する必要はありませんか？グラフが無向グラフであれば、両方向のエッジを持つ有向グラフになります。

Answer 1

はい、Dijkstraのアルゴリズムは両方のタイプのグラフで動作し、無向グラフの場合は両方の端点からエッジを使用することができます。

あなたの実装が隣接リストによって与えられたグラフで動作する場合、この情報は既にこのデータ構造によって暗黙的に与えられています：あなたが指定した無関係のケースでは、エッジ（u、v） vはあなたに両方向を与えるuの隣にあります。したがって、両方のタイプのグラフで同じ実装を使用できます。