Floyd의 최단 경로 알고리즘은 그래프의 모든 정점 간의 최단 경로를 한 번에 찾아준다.
알고리즘 자체는 매우 간단하다. 2차원 배열 A를 이용하여 3중 반복을 하는 구성이다.

// Floyd의 최단 경로 알고리즘 의사 코드
Floyd(G):
  for k <- 0 to n - 1
    for i <- 0 to n - 1
      for j <- 0 to n - 1
        A[i][j] = min(A[i][j], A[i][k] + A[k][j])

설명

Ak[i][j]를 0부터 k까지의 정점만을 이용한 정점 i에서 j까지의 최단 경로라고 하자.
이 Ak[i][j]는 다음의 2가지로 나누어 생각할 수 있다.

Floyd

  1. 정점 k를 거치지 않는 경우: 기존 경로 유지
    이때 최단 거리는 Ak-1[i][j]가 된다.

  2. 정점 k를 거치는 경우: 경로 변경
    i에서 k까지의 최단거리 Ak-1[i][k]에다가 k에서 j까지의 최단거리인 Ak-1[j][k]를 더한 값이 된다.

즉, Ak[i][j] = min(Ak-1[i][j], Ak-1[i][k] + Ak-1[k][j])가 된다.

이는 정점 k를 경유하는 것이 더 짧은 경로이면 Ak-1[i][j]의 값이 변경되고,
그렇지 않으면 이전 값을 유지한다는 의미이다.

자바스크립트로 구현

자바스크립트로 구현할 그래프는 다음과 같다.

그래프

이 그래프를 인접 행렬로 구현하기 위해 클래스를 작성한다.
위에서 설명한 A 배열은 distance 배열이 담당하도록 하였다.

// Floyd의 최단 경로 알고리즘
// 무방향 그래프 (인접 행렬)
class Graph {
  constructor(size = 1) {
    this.size = size;

    // 2차원 배열 생성
    this.matrix = []; // 원본 데이터
    for (let i = 0; i < size; i++) {
      this.matrix.push([]);
      for (let j = 0; j < size; j++) {
        if (i === j) this.matrix[i][j] = 0; // 자신은 0으로 초기화
        else this.matrix[i][j] = Infinity; // 다른 정점들은 Infinity로 초기화
      }
    }
    this.distance = []; // 최단 경로를 저장할 배열
  }

  // 간선 삽입 메서드
  addEdge(vertex1, vertex2, weight) {
    if (vertex1 > this.size - 1 || vertex2 > this.size - 1) {
      throw new TypeError('Invalid vertex');
    } else if (vertex1 === vertex2) {
      throw new TypeError('Same vertex');
    } else {
      this.matrix[vertex1][vertex2] = weight;
      this.matrix[vertex2][vertex1] = weight;
    }
  }

이어서 결과를 출력하는 메서드, 그리고 floyd의 최단 경로 알고리즘을 구현하였다.
위에서 설명한 의사 코드와 비교해보자.

  // 행렬을 출력하는 메서드
  print(matrix) {
    for (let i = 0; i < this.size; i++) {
      let result = '';
      for (let j = 0; j < this.size; j++) {
        if (matrix[i][j] === Infinity) result += '* ';
        else result += `${matrix[i][j]} `;
      }
      console.log(result);
    }
  }

  // floyd의 최단 경로 알고리즘
  floyd() {
    // 최단경로를 갱신하여 저장하는 배열
    this.distance = this.matrix; // 초기화

    for (let k = 0; k < this.size; k++) {
      for (let i = 0; i < this.size; i++) {
        for (let j = 0; j < this.size; j++) {
          if (this.distance[i][k] + this.distance[k][j] < this.distance[i][j]) {
            this.distance[i][j] = this.distance[i][k] + this.distance[k][j];
          }
        }
      }
    }
    this.print(this.distance);
  }
}

이제 간선을 삽입하여 원본 그래프를 구현한 뒤, floyd 메서드를 호출한다.

const graph = new Graph(7);
// 간선 삽입
graph.addEdge(0, 1, 7);
graph.addEdge(0, 4, 3);
graph.addEdge(0, 5, 10);
graph.addEdge(1, 2, 4);
graph.addEdge(1, 3, 10);
graph.addEdge(1, 4, 2);
graph.addEdge(1, 5, 6);
graph.addEdge(2, 3, 2);
graph.addEdge(3, 4, 11);
graph.addEdge(3, 5, 9);
graph.addEdge(3, 6, 4);
graph.addEdge(4, 6, 5);
graph.floyd();

결과는?

결과

짠!

시간복잡도

Floyd 알고리즘은 삼중 for문으로 구성되므로, 시간복잡도는 O(n3)이다. (n은 정점을 의미)

참고로 Dijkstra의 알고리즘을 n번 반복하면 모든 정점상의 최단경로를 구할 수 있다.
이 경우 전체 복잡도는 O(n3)으로 Floyd와 동일하다.

정리

  • Dijkstra의 알고리즘
    하나의 정점으로부터 모든 다른 정점까지의 최단 경로를 구할 때
  • Floyd의 알고리즘
    모든 정점 간의 최단경로를 구할 때

참고(References)

천인국, “C언어로 쉽게 풀어 쓴 자료구조”, 경기도: 생능, 2019, pp. 425-430