Chapter 95

ダイクストラ法

miku
miku
2021.11.20に更新

重み付きグラフ

辺に重みが付いているグラフのことを重み付きグラフと呼び、上記のような形となる。重みは頂点間の移動距離や時間を表しており、上記のABCDの各頂点は駅名、辺の数字は駅間の移動時間だと考えてみる。

たとえばA駅からD駅までを最短の時間で移動したい場合、A駅からD駅へと直接移動すると20分かかるが、A駅->B駅->C駅->D駅と移動すると18分で済む。

このように重み付きグラフの場合、移動する頂点の数が短かければ最短経路になるとは限らない。これから説明するダイクストラ法は重み付きグラフにおいて最短経路を求めるアルゴリズムとなる。ただし辺の重みに負数が含まれる場合はダイクストラ法を利用することはできない。

ダイクストラ法

新たに重み付きグラフを用意して、頂点Aが始点だとする。

頂点Aから開始をしているので、当然ながら頂点Aまでの最短距離は 0 になる。

画像ではわかりやすいように、確定した頂点の付近にその頂点までの最短距離を書き、頂点の色を赤に変更している。

  • 確定頂点: [A]
  • Aまでの最短距離: 0 / ルート: [A] (確定)

最短経路が確定した頂点Aに繋がっている頂点に頂点Aからの距離を書き加えておく。
(A-B / A-F / A-E間の距離を、各頂点に保持しておく。)

頂点Aに繋がっているこれらの頂点は次に最短経路が確定するかもしれない未確定頂点になる。画像ではわかりやすいように、未確定頂点の色とルートを青色に変更している。

  • 未確定頂点: [B, F, E]
  • 確定頂点: [A]
  • A までの最短距離: 0 / ルート: [A] (確定)
  • B までの最短距離: 9 / ルート: [A-B] (未確定)
  • F までの最短距離: 4 / ルート: [A-F] (未確定)
  • E までの最短距離: 3 / ルート: [A-E] (未確定)

開始地点から一番短い経路で繋がっている未確定頂点を探す。

A-B / A-F / A-Eの中では、A-E間の距離が一番短いので、頂点Eまで移動するには、A-E間が最短であることが確定する。

何故かというと最短経路が確定している頂点Aに繋がっている頂点の中で、一番短い経路がA-Eなので、他の経路、たとえばA-FやA-Bから頂点Eの方に周りこんだルートがA-Eより小さくなることはありえないからである。

  • 未確定頂点: [B, F]
  • 確定頂点: [A, E]
  • A までの最短距離: 0 [A] (確定)
  • B までの最短距離: 9 [A-B] (未確定)
  • F までの最短距離: 4 [A-F] (未確定)
  • E までの最短距離: 3 [A-E] (確定)

最短経路が確定した頂点Eに繋がっている頂点Dと頂点Fに注目する。

頂点Dは新しく繋がった未確定頂点である。それに加え、頂点Eには 3 という始点からの距離が保持されているが、それにE-D間の距離を足した 8 を頂点Dに書き込んでおく。

つまり、まだ未確定だが、開始地点からの最短距離を暫定的に頂点に書き込んでおく。

頂点Fはすでに候補になっている頂点なので、開始地点から頂点Fまでの暫定的な最短距離 4 が書き込まれている。それがさらに短くできるならば更新を行う。

A-E-Fの距離は 5 だが、もともと存在していたA-Fの経路の方が短いので、頂点Fまでの暫定的な最短距離の情報は更新をしない。

今のところ、未確定だが頂点Fまでの最短経路はA-Fのままとなる。

  • 未確定頂点: [B, D, F]
  • 確定頂点: [A, E]
  • A までの最短距離: 0 [A] (確定)
  • B までの最短距離: 9 [A-B] (未確定)
  • D までの最短距離: 8 [A-E-D] (未確定)
  • F までの最短距離: 4 [A-F] (未確定)
  • E までの最短距離: 3 [A-E] (確定)

開始地点から一番短い経路で繋がっている未確定頂点を探す。

A-B / A-F / A-E-Dの中では、A-F間の距離が一番短いので、頂点Fまで移動するには、A-F間が最短であることが確定する。

  • 未確定頂点: [B, D]
  • 確定頂点: [A, E, F]
  • A までの最短距離: 0 [A] (確定)
  • B までの最短距離: 9 [A-B] (未確定)
  • D までの最短距離: 8 [A-E-D] (未確定)
  • F までの最短距離: 4 [A-F] (確定)
  • E までの最短距離: 3 [A-E] (確定)

最短経路が確定した頂点Fに繋がっている頂点Bと頂点Dに注目する。

頂点Bと頂点Dに書き込まれている最短距離より、A-Fから通る距離の方が短ければ、情報を更新する。

頂点Bの場合、A-Bの距離 9 よりA-F-Bの距離 7 の方が短いので、頂点Bまでの最短経路が 7 に更新される。

頂点Dの場合、A-E-Dの距離 8 より A-F-Dの距離 9 の方が長いので、頂点Dまでの最短経路は 8 のままになる。

  • 未確定頂点: [B, D]
  • 確定頂点: [A, E, F]
  • A までの最短距離: 0 [A] (確定)
  • B までの最短距離: 7 [A-F-B] (未確定)
  • D までの最短距離: 8 [A-E-D] (未確定)
  • F までの最短距離: 4 [A-F] (確定)
  • E までの最短距離: 3 [A-E] (確定)

開始地点から一番短い経路で繋がっている未確定頂点を探す。

A-B / A-E-Dの中では、A-B間の距離が一番短いので、頂点Bまで移動するには、A-B間が最短であることが確定する。

  • 未確定頂点: [D]
  • 確定頂点: [A, B, E, F]
  • A までの最短距離: 0 [A] (確定)
  • B までの最短距離: 7 [A-F-B] (確定)
  • D までの最短距離: 8 [A-E-D] (未確定)
  • F までの最短距離: 4 [A-F] (確定)
  • E までの最短距離: 3 [A-E] (確定)

最短経路が確定した頂点Bに繋がっている頂点Cに注目する。

頂点Cは新しく繋がった未確定頂点である。

頂点Bまでの最短距離 7 にB-C間の距離を足した 11 を頂点Cに書き込んでおく。

  • 未確定頂点: [C, D]
  • 確定頂点: [A, B, E, F]
  • A までの最短距離: 0 [A] (確定)
  • B までの最短距離: 7 [A-F-B] (確定)
  • C までの最短距離: 11 [A-F-B-C] (未確定)
  • D までの最短距離: 8 [A-E-D] (未確定)
  • F までの最短距離: 4 [A-F] (確定)
  • E までの最短距離: 3 [A-E] (確定)

開始地点から一番短い経路で繋がっている未確定頂点を探す。

A-F-B-C / A-E-Dの中では、A-E-D間の距離が一番短いので、頂点Dまで移動するには、A-E-D間が最短であることが確定する。

  • 未確定頂点: [C]
  • 確定頂点: [A, B, D, E, F]
  • A までの最短距離: 0 [A] (確定)
  • B までの最短距離: 7 [A-F-B] (確定)
  • C までの最短距離: 11 [A-F-B-C] (未確定)
  • D までの最短距離: 8 [A-E-D] (確定)
  • F までの最短距離: 4 [A-F] (確定)
  • E までの最短距離: 3 [A-E] (確定)

最短経路が確定した頂点Dに繋がっている頂点Cに注目する。

頂点Cに書き込まれている最短距離より、A-E-Dから通る距離の方が短ければ、情報を更新する。

頂点Cの場合、A-F-B-Cの距離 11 より A-E-D-Cの距離 10 の方が短いので、頂点Cまでの最短経路が 10 に更新される。

  • 未確定頂点: [C]
  • 確定頂点: [A, B, D, E, F]
  • A までの最短距離: 0 [A] (確定)
  • B までの最短距離: 7 [A-F-B] (確定)
  • C までの最短距離: 10 [A-E-D-C] (未確定)
  • D までの最短距離: 8 [A-E-D] (確定)
  • F までの最短距離: 4 [A-F] (確定)
  • E までの最短距離: 3 [A-E] (確定)

開始地点から一番短い経路で繋がっている未確定頂点を探す。

未確定なのは頂点Cしか残っていないので、頂点Cまで移動するには、A-E-D-C間が最短であることが確定する。

  • 未確定頂点: []
  • 確定頂点: [A, B, C, D, E, F]
  • A までの最短距離: 0 [A] (確定)
  • B までの最短距離: 7 [A-F-B] (確定)
  • C までの最短距離: 10 [A-E-D-C] (確定)
  • D までの最短距離: 8 [A-E-D] (確定)
  • F までの最短距離: 4 [A-F] (確定)
  • E までの最短距離: 3 [A-E] (確定)

ダイクストラ法の実装例

const INF = 1000000000;
const n = 4; // 頂点数
const start = 0; // 始点
const edge = new Array(n).fill().map(() => []);
const queue = [];

// 移動するのにcostかかる頂点fromから頂点toへの辺を追加
function addEdge(from, to, cost) {
  edge[from].push({ to, cost });
}

// 始点から頂点iまでcostかかる情報を追加
function pushQueue(i, cost) {
  queue.push({ i, cost });
}

// queueから最小のcostを持つオブジェクトを取り出す
function popQueue() {
  let minCost = INF;
  let minIndex = -1;
  for (let i = 0; i < queue.length; i++) {
    const o = queue[i];
    if (o.cost < minCost) {
      minCost = o.cost;
      minIndex = i;
    }
  }

  return queue.splice(minIndex, 1)[0];
}

// 辺の登録。例えば一番上は頂点0から頂点1まで移動するのにコストが1かかることを表している
addEdge(0, 1, 1);
addEdge(0, 2, 4);
addEdge(1, 2, 2);
addEdge(2, 3, 1);
addEdge(1, 3, 5);

// 始点から各頂点までの移動総コスト
// 始点は0、それ以外の頂点は入ることがあり得ない大きい値にしておく
const dist = new Array(n).fill(INF);
dist[start] = 0;

pushQueue(start, 0);

// キューが空になるまでループ
while (queue.length > 0) {
  // 未確定の頂点の中から始点からの移動総コストが最小のものを取り出す
  // この時点で、始点から取り出した頂点までの最短コストが確定する
  const o = popQueue();
  const cur = o.i;
  const cost = o.cost;

  // 既にcostより小さい値で確定されているのでスキップ
  if (dist[cur] < cost) {
    continue;
  }

  // 取り出した頂点に繋がっている各頂点を走査
  for (const next of edge[cur]) {
    // 計算したコストが暫定コストより小さければ更新。
    // 次の頂点をキューに追加する
    const newCost = dist[cur] + next.cost;
    if (newCost < dist[next.to]) {
      dist[next.to] = newCost;
      pushQueue(next.to, newCost);
    }
  }
}

console.log(dist);

queue 配列に同じ頂点を追加した際、既に入っている同じ頂点の情報が上書きされるなどのようなことが起き得ないので、確定した頂点なのにまたキューからその頂点が出てくるということがある。その場合、無駄な走査を行わないように、if (dist[cur] < cost) ならスキップを行うという処理を入れるのがポイントとなる。

queue 配列から最小のコストを持つ、頂点とコストのペアのオブジェクトを取り出す際、配列を走査をするのに毎回配列の長さ分だけ時間がかかるので、できれば優先度付きキューというデータ構造を利用したほうがいい。ただし、そのデータ構造はJavaScriptでは標準で定義されていないので自前で実装するかnpmに登録されているものを利用する必要がある。