【TypeScript】高速に最短距離を計算するアルゴリズム『ワーシャルフロイド』

ワーシャルフロイド（Warshall–Floyd）というアルゴリズムがあります。
最短経路探索の一種です。

最短経路探索とは

最短経路探索とはこのような問題のことです。

街が５個あります。
街と街の間は道で繋がっています。
街１から街５への最短距離を求めてください。

この図では4のようですね。

ワーシャルフロイドの長所

ワーシャルフロイドは、全ての街から街への距離をいっぺんに求められるアルゴリズムです。
街が5個ある場合は全部で10通りのペアが存在しますね。
この10通り全てを高速に計算してくれます。
計算量は街の数の3乗です。

他の最短経路探索のアルゴリズムとしてダイクストラ法が有名です。
ダイクストラ法は特定の『ある街からある街への距離』を求めるのが得意なアルゴリズムです。
計算量は(街の数+道の数)*log(街の数)です。

つまり問題の種類によって

• 街1から街5への距離を求めなさい => ダイクストラ法を使う
• 全ての街から全ての街への距離を求めなさい => ワーシャルフロイドを使う

という使い分けをすればいいですね。

実装

classを使いました。

使い方

• 道の情報を入力
• build
• 答えを得る

コード

class WarchallFloyd {
  private distances: number[][];

  constructor(private n: number) {
    this.distances = new Array(n);
    for (let i = 0; i < n; i++) this.distances[i] = new Array(n);
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        this.distances[i][j] = NaN;
      }
    }
    for (let i = 0; i < n; i++) this.distances[i][i] = 0;
  }

  min(a: number, b: number) {
    console.assert(!(isNaN(a) && isNaN(b)));
    if (isNaN(a)) return b;
    if (isNaN(b)) return a;
    return Math.min(a, b);
  }

  build() {
    for (let k = 0; k < this.n; k++) {
      // 経由する頂点
      for (let i = 0; i < this.n; i++) {
        // 始点
        for (let j = 0; j < this.n; j++) {
          // 終点
          if (
            isNaN(this.distances[i][j]) &&
            (isNaN(this.distances[i][k]) || isNaN(this.distances[k][j]))
          ) {
            this.distances[i][j] = NaN;
          } else {
            this.distances[i][j] = this.min(
              this.distances[i][j],
              this.distances[i][k] + this.distances[k][j]
            );
          }
        }
      }
    }
  }

  answer(from: number, to: number): number {
    return this.distances[from][to];
  }

  add(from: number, to: number, cost: number) {
    this.distances[from][to] = cost;
    this.distances[to][from] = cost;
  }
}

例

const wf = new WarchallFloyd(5);
wf.add(0, 1, 3);
wf.add(1, 4, 2);
wf.add(0, 2, 1);
wf.add(1, 2, 5);
wf.add(2, 3, 2);
wf.add(3, 4, 1);
wf.build();

for (let i = 0; i < 5; i++) {
  const res = [];
  for (let j = 0; j < 5; j++) {
    res.push(wf.answer(i, j));
  }
  console.log(res);
}


// out
[ 0, 3, 1, 3, 4 ]
[ 3, 0, 4, 3, 2 ]
[ 1, 4, 0, 2, 3 ]
[ 3, 3, 2, 0, 1 ]
[ 4, 2, 3, 1, 0 ]