[TypeScript] 고속 최단 거리를 계산하는 알고리즘 "workroid"

Warshall – Flowyd라는 알고리즘이 있습니다.
가장 짧은 노선 탐색의 일종이다.

최단 경로 탐색

최단 노선 탐색이 바로 이런 문제다.

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

이 그림은 4인 것 같아요.

로봇의 장점

화사브로드는 모든 거리와 거리의 거리를 동시에 요구하는 알고리즘이다.
다섯 개의 거리가 있으면 모두 열 쌍이 있다.
이 열 가지는 모두 고속 계산을 할 줄 안다.
계산량은街の数の3乗이다.
다른 가장 짧은 경로 탐색 알고리즘으로 X법이 유명하다.
옥스포드법은 특정한'어떤 거리에서 어떤 거리까지의 거리'를 찾는 데 뛰어난 알고리즘이다.
계산량은(街の数+道の数)*log(街の数)이다.
그러니까 문제의 종류에 따라.

거리 1에서 거리 5까지의 거리 요청=>잠수법 사용

모든 거리에서 모든 거리로 거리를 찾으세요=>바르샤바 로봇

사용
이렇게 구분하면 됩니다.

이루어지다

클라스를 사용했습니다.

사용법

도로 정보 입력

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 ]