ダイクストラ法とは
だいくすとらほう
辺の重みが0以上のグラフで、1つの出発点から各頂点への最短経路を求めるアルゴリズム。距離が確定していない頂点のうち最も近いものを確定し、その隣の頂点の距離を更新することを繰り返す。負の重みの辺があると正しく求められない。
「ダイクストラ法」は、1分野の3問の練習問題に出てきます(データ構造とアルゴリズムなど)。
この用語の分野: データ構造とアルゴリズム
手順
出発点の距離を0、ほかの頂点を無限大とし、すべての頂点を未確定にします。未確定の頂点のうち距離が最小のものを1つ選んで確定し、その頂点から出る辺について、「確定した距離 + 辺の重み」がその先の頂点の今の距離より小さければ更新します(緩和)。これを全頂点が確定するまで繰り返します。更新したときに直前の頂点を記録しておけば、最短経路そのものを後からたどれます。
計算量と優先度付きキュー
最小の頂点を毎回すべての頂点から探すと、頂点数 V に対して O(V²) かかります。二分ヒープによる優先度付きキューを使うと、辺の数を E として O((V + E) log V) になり、道路網のように辺の少ないグラフで大幅に速くなります。グラフは隣接リストで持つのが普通です。カーナビの経路探索では、目的地への見込みの距離を加えて探索を目的地の方向に絞るA*探索や、前もって計算した情報を使う高速化の手法が組み合わされています。
負の重みと他のアルゴリズム
ダイクストラ法は、ほかの頂点を経由すると距離が増えることはあっても減らない、という前提で頂点を確定させるので、負の重みの辺があると、確定した距離が後から短くなることがあり、正しい答えが保証されません。負の重みがある場合は、すべての辺の緩和を V−1 回繰り返すベルマン・フォード法を使い、負の閉路の検出もできます。すべての頂点の組の最短経路には、動的計画法によるフロイド・ワーシャル法(O(V³))も使われます。ネットワークのルーティングでは、OSPFなどのリンクステート型のプロトコルが各ルータでダイクストラ法を使って経路を計算します。
ダイクストラ法の練習問題に挑戦
辺に向きのないグラフで、辺の重み(距離)が S−A: 4、S−B: 1、A−B: 2、A−C: 1、B−C: 5、C−T: 3、A−T: 6 である。ダイクストラ法で S から T までの最短経路を求めたとき、その経路と長さはどれか。
- AS→A→C→T、長さ8
- BS→B→A→C→T、長さ7
- CS→B→C→T、長さ9
答えと解説を見る
正解：B. S→B→A→C→T、長さ7
ダイクストラ法は、距離が確定していない頂点のうち最も近いものを確定し、その隣の頂点の距離を更新することを繰り返します。S(0)から B が1で確定し、B を通ると A は 1 + 2 = 3 で直接の4より短くなります。A(3)を確定すると C は 3 + 1 = 4、T は 3 + 6 = 9 になり、C(4)を確定すると T は 4 + 3 = 7 に更新されます。したがって最短経路は S→B→A→C→T で長さは7です。S→A→C→T(8)は S−A を直接通る分だけ長く、S→B→C→T(9)は B−C の5が大きいため長くなります。
ダイクストラ法で正しい最短経路が求められるための、グラフについての条件として正しいものはどれか。
- Aグラフに閉路(同じ頂点に戻ってくる経路)がないこと
- B辺に向きがないこと
- C辺の重みがすべて0以上であること
答えと解説を見る
正解：C. 辺の重みがすべて0以上であること
ダイクストラ法は、未確定の頂点のうち最も距離の小さいものを確定させます。これは、ほかの頂点を経由すると距離が増えることはあっても減ることはない、という前提に基づいています。負の重みの辺があると、後から別の経路で距離が短くなることがあり、例えば S→A が2、S→B が3、B→A が−2 の有向グラフでは、A を2で確定した後に S→B→A の1が見つかります。負の重みがあるときはベルマン・フォード法などを使います。閉路があっても、辺に向きがあっても、重みが0以上であればダイクストラ法は使えます。
よくある質問
ダイクストラ法と幅優先探索の関係は何ですか?
すべての辺の重みが1なら、ダイクストラ法は幅優先探索と同じ順に頂点を確定します。重みが異なる場合に、キューの代わりに距離の小さい順に取り出す優先度付きキューを使うよう一般化したものと考えられます。
ダイクストラ法は辺の向きのあるグラフにも使えますか?
使えます。重みが0以上であれば、有向グラフでも無向グラフでも、閉路があっても正しい最短経路が求まります。
解説の中の「ダイクストラ法」
ダイクストラ法は、距離が確定していない頂点のうち最も近いものを確定し、その隣の頂点の距離を更新することを繰り返します。
辺に向きのないグラフで、辺の重み(距離)が S−A: 4、S−B: 1、A−B: 2、A−C: 1、B−C: 5、C−…ダイクストラ法は、未確定の頂点のうち最も距離の小さいものを確定させます。
ダイクストラ法で正しい最短経路が求められるための、グラフについての条件として正しいものはどれか。幅優先探索やダイクストラ法のように、頂点から出る辺を順にたどる処理では、隣接リストの方が効率よく動きます。
頂点が100万個、辺が300万本ほどの道路網のように、頂点の数に比べて辺の少ない(疎な)グラフをメモリに記憶する方法と…
「ダイクストラ法」が出てくる問題(3問)
データ構造とアルゴリズムの参考書を探す PR
Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。