플로이드 워셜의 정의

플로이드 워셜(Floyd-Warshall) 알고리즘은 그래프에서 모든 노드 쌍 간의 최단 경로를 찾는 알고리즘이다. 가중치가 있는 그래프에서 사용될 수 있으며, 동적 프로그래밍 기법을 기반으로 한다. 이 알고리즘은 각 노드를 중간 노드로 하여 다른 모든 노드 쌍 사이의 가능한 최단 경로를 반복적으로 갱신한다.

• 시간 복잡도: 𝑂(𝑛^3)
• 공간 복잡도: 𝑂(𝑛^2)

문제 유형

주로 다음과 같은 유형의 문제에 적용된다.

• 작은 그래프에서의 모든 쌍 최단 경로 문제
• 경로 재구성
• 트랜지티브 클로저 (한 노드에서 다른 노드로 도달 가능한지 결정)
• 중간 노드를 경유하는 경로 분석
• 응용 네트워크 분석
• 음수 가중치가 있는 그래프 (단, 음의 사이클이 없는 경우)

주의사항

• 노드의 수가 많을 경우 매우 느려질 수 있으므로, 대규모 그래프가 아닐 경우에만 사용한다.
• 2차원 배열을 사용하기 때문에 노드의 수가 많을 때 많은 메모리를 필요로 한다.

• n이 100 이하: 플로이드 워셜 알고리즘을 사용하자.
• n이 200~300 : 이 때는 프로그램의 성능과 실행 시간 제한을 고려해야 한다. 최악의 경우 연산 수가 27,000,000 까지 도달할 수 있습니다.
• n이 400 이상: 플로이드 워셜 알고리즘을 쓰지 않는다!

플로이드 워셜을 쓰지 말아야 할 유형

• 매우 큰 그래프에서의 문제 (다익스트라일 수 있다!)
• 단일 출발점 또는 목표 지점 최단 경로 문제
• 음의 사이클이 있는 그래프 (벨만-포드 알고리즘)
• 메모리 리소스 제약이 심한 문제

플로이드 워셜 node.js 구현

백준 경로 찾기 문제를 플로이드 워셜로 구현해보자.

구현 순서

1️⃣ 초기화

• 도달 가능성을 나타내는 2차원 배열을 초기화한다.

2️⃣ 플로이드 워셜 알고리즘 적용

• 모든 노드 쌍에 대해 경로가 존재하는지 확인하고, 중간 노드를 이용하여 간접적인 연결을 찾아 행렬을 업데이트한다.

3️⃣ 결과 출력

플로이드 워셜

이 순서 중 2️⃣번을 자세히 살펴보자!

플로이드 워셜은 3중 for문을 사용하는 것이 특징이다.

for (let k = 0; k < n; k++) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (graph[i][j] === 1 || (graph[i][k] === 1 && graph[k][j] === 1)) {
        graph[i][j] = 1;
      }
    }
  }
}

• 모든 노드를 중간 노드(k), 출발 노드(i), 도착 노드(j) 로 설정하여 경로를 찾는다.

• if 문에서는 도달 가능성을 평가한다. graph[i][k] === 1 && graph[k][j] === 1조건을 만족하면 i에서 j로의 경로도 존재하는 것이므로 graph[i][j]를 1로 설정한다.

전체 코드

// 1초, 256MB
// 정점의 개수 N (1 ≤ N ≤ 100) <-- 플로이드 워셜 사용 적합

const fs = require("fs");
const [[N], ...graph] = fs
  .readFileSync("./input.txt")
  .toString()
  .split("\n")
  .map((line) => line.split(" ").map(Number));

for (let k = 0; k < graph.length; k++) {
  for (let i = 0; i < graph.length; i++) {
    for (let j = 0; j < graph.length; j++) {
      if (graph[i][k] === 1 && graph[k][j] === 1) graph[i][j] = 1;
    }
  }
}

console.log(graph.map((arr) => arr.join(" ")).join("\n"));