プログラミング原人の進化ログ

プログラミング原人の進化論

オレ プログラミング ベンキョウ スル。マナンダ コト カク。

ダイクストラ法で最短経路を求める

最短経路問題をやります。最短経路を求めるアルゴリズムとして、ダイクストラ法を取り上げます。最後に問題を解きます。

最短経路問題

重み付きグラフが与えられているとします。最短経路問題とは、ある2点間をつなぐパスを構成する辺の重みの総和が最小となるようなパスを求める問題です。

  • 単一始点最短経路問題:ある1つの頂点から、他の全ての頂点への最短経路を求める。
  • 全点対間最短経路問題:全ての頂点のペアに関して、最短経路を求める。

頂点sから他の全ての頂点へ最短経路を構成したとします。頂点sから他の頂点への最短経路を重ね合わせると、頂点sを根とする全域木となります。この全域木を最短経路木と言います。

ダイクストラ

ダイクストラは最短経路問題を解くアルゴリズムです。グラフに含まれる頂点全体の集合をV、最短経路木に含まれる頂点の集合をSとすると、以下のようなアルゴリズムとなります。

  • 始点のコストを0、それ以外の頂点のコストをINFTYにする。INFTYは十分大きい値(最短経路の辺の重みの和より大きいならOKだと思います、おそらく)。
  • S = V となるまで以下を繰り返す:
    • V-Sから、コストが最小の頂点uを選ぶ。
    • uをSに追加する。さらに、V - S に属し、かつuに隣接している頂点vのコストを更新する。具体的には、頂点xのコストをcost(x)、頂点xからyへの辺の重みをw(x, y)と書くと、

cost(v) > cost(u) + w(u, v) \Rightarrow cost(v) = cost(u) + w(u, v)

上のアルゴリズムは、当然、辺の重みが非負でなければなりません。

こちらの記事だとダイクストラ法のイメージがとても掴みやすいと思います。

問題を解いてみる

以下の問題を解きます。言語はC++です。

最短経路 ダイクストラ法 | アルゴリズムとデータ構造 | Aizu Online Judge

・コストは距離dです。

・存在しない辺の重みはINFTYにしておきます。

・各頂点の状態を管理するために次のように色を用います。

  • black:Sに属する
  • gray :Sに属する頂点のいずれかに隣接する
  • white:それ以外

解答例:

#include<iostream>
using namespace std;

#define N 100
#define INFTY 10000001
#define WHITE 0
#define GRAY 1
#define BLACK 2

// ダイクストラ法を適用し、dを更新する関数
void dijkstra(int n, int d[], int M[N][N]) {
  int i, vertex, min_d, color[N];
  // 初期状態
  for (i = 0; i < n; i++) {
    d[i] = INFTY;
    color[i] = WHITE;
  }
  d[0] = 0;
  color[0] = GRAY;

  while (1) {
    // S - V でコスト最小の頂点を選ぶ
    vertex = -1;
    min_d = INFTY;
    for (i = 0; i < n; i++) {
      if (color[i] == GRAY && d[i] < min_d) {
        min_d = d[i];
        vertex = i;
      }
    }
    // S = V の場合は終了
    if (vertex == -1) break;

    // vertexをSに追加
    color[vertex] = BLACK;

    // S-Vに属し、vertexに隣接する頂点のコストを更新
    for (i = 0; i < n; i++) {
      if (color[i] != BLACK && M[vertex][i] < INFTY) {
        color[i] = GRAY;
        if (d[i] > d[vertex] + M[vertex][i]) {
          d[i] = d[vertex] + M[vertex][i];
        }
      }
    }
  }
}

int main() {
  int i, j, n, u, k, v, c, d[N], M[N][N];

  cin >> n;
  // 隣接行列を作る
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      M[i][j] = INFTY;
    }
  }
  for (i = 0; i < n; i++) {
    cin >> u >> k;
    for (j = 0; j < k; j++) {
      cin >> v >> c;
      M[u][v] = c;
    }
  }

  // ダイクストラ法
  dijkstra(n, d, M);

  for (i = 0; i < n; i++) cout << i << " " << d[i] << endl;    

  return 0;
}

まとめ

INFTYの大きさをちゃんと考えないとひっかかるかも。 あとは、具体的なグラフを題材に自分で手を動かしてみないとイメージは掴みづらいかなぁと。それさえできれば実装はそんなに難しくないと思います。

参考

ダイクストラ法(最短経路問題)

渡部有隆. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. Ozy, 秋葉拓哉協力. 株式会社マイナビ. 2015.