ACM-ICPC

ダイクストラ法


グラフ問題では良く出てくる、ダイクストラ法について説明します。
そんな大事なのを、なぜ本番前に説明しなかったのかって?
・・・すみませんでした。

ダイキストラ法とは?

辺が長さをもつグラフ(有向・無向どちらも可)について、ある1点までの最短距離を求める方法です。このダイクストラ法のメリットは、すべての点からある1点までの最短距離を、頂点数の2乗くらいの時間で求められることです。

基本的な方針

まず、目的地Gのコスト(目的地までの最短距離を覚えておく)をゼロに、それ以外の点のコストを+∞に初期化しておきます。それと、全ての点を「未使用」にしておきます。

次に、「未使用の中でコストが最小」の点Yを探します。(最初はもちろん目的地)見つかったら、点Yにつながる全ての点Xに対し、Xの現在のコストより「X→Yの距離」+「Yのコスト」の方が小さければそれで更新します。そして、Yを「使用済み」にします。

これを、未使用の点がなくなるか最小値が+∞になるまで繰り返します。

とにかく、ダイクストラには「初期化」「最小値検索」「更新」の3つのパートがあると覚えておくと良いでしょう。


文章だけではわかりにくいので、次のようなグラフで実際に求めてみましょう。
目的地は一番右の点Eとします。


まず初期化。コストを0と∞に設定し、すべて未使用にします。


未使用の点の中でコストが最小なのはEです。Eへとつながる点B,Dを更新し、Eを使用済みにします。


次の最小点はBです。同様に点A,C,Dを更新します。


次はA。3+7>7のため、Dは書き換えられません。


C。


D。そして終了。


プログラム例

nには頂点数、dist[x][y]には、x→yの辺があるところにはその長さ、無いところは+∞を入れておきます。実際に+∞という記述は使えないので、具体的な値を設定します。全ての辺の長さの合計より大きければ問題無いでしょう。ただ、int型の場合あまり大きいと加算したときオーバーフローしてしまうので、2つ足してもOFしない10億くらいがよいでしょう。
この関数dijkstraを実行すると、cost[x]に目的地gまでの最短距離が入ります。xから目的地gまでいけないときは+∞のままになります。
ちなみに、dijkstraは綴りミスじゃありませんよ。念のため。

#define INF 1000000000
int n;
int dist[100][100];
int cost[100];
char used[100];

void dijkstra(int g)
{
 int x, y, min;
 for(x = 0; x < n; x++){
  cost[x] = INF;
  used[x] = 0;
 }
 cost[g] = 0;
 while(1){
  min = INF;
  for(x = 0; x < n; x++){
   if(!used[x] && min > cost[x])
    min = cost[x];
  }
  if(min == INF)
   break;
  for(y = 0; y < n; y++){
   if(cost[y] == min){
    for(x = 0; x < n; x++){
     if(cost[x] > dist[x][y] + cost[y])
      cost[x] = dist[x][y] + cost[y];
    }
   }
  }
 }
}


最短ルートを求める

目的地以外の全ての点において、コストを更新するときにどこから更新したかを覚えておきます。(next[]などの配列を用意します。)それをたどることで目的地までの最短ルートを得ることが出来ます。