[최단경로] 플로이드-워셜(Floyd-Warshall) 알고리즘

🍀 목차
플로이드-워셜 알고리즘
같은 목적을 가진 알고리즘
기본 이해
구현(JavaScript)
그냥 다익스트라를 정점만큼 돌리면 안 되나요?
시간 복잡도

플로이드-워셜 알고리즘

• 가중 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 최단 경로를 찾기 위한 알고리즘 중 하나.
• 한 번 실행하여 모든 정점 - 모든 정점 간의 최단 경로를 구할 수 있는 알고리즘.
• 다이나믹 프로그래밍(DP)을 바탕으로 하고 있다.
• 음의 사이클이 없는 그래프라면 음의 가중치를 가졌을 때도 사용 가능. (음의 사이클의 존재를 판단할 수 있음.)

같은 목적을 가진 알고리즘 

 다익스트라 알고리즘 게시글에 정리해놓았다.

기본 이해

 모든 정점과 모든 정점 간의 최단 거리를 구해야 하므로 2차원 배열을 생성, 갱신해 나간다. 단계별로 모든 정점을 거쳐 가는 경우를 확인한다. 정점 A에서 B로 가는 최단 거리보다 A에서 특정 정점 K를 거쳐 B로 가는 거리가 더 짧다면 갱신한다. 특정 정점 K는 보통 '경유지'로 표현된다. 즉, K를 정해 dist[A][B]와 dist[A][K]+dist[K][B]를 비교해 나가는 것.

 

 플로이드-워셜 알고리즘은 다음과 같은 순서로 실행된다. 

 

1. 현재 정점에서 다른 정점으로 바로 가는 경로가 있다면 배열에 최소 비용을, 갈 수 없다면 INF 값을 저장한다.

 위의 그래프의 모든 정점과 모든 정점 사이의 최단 경로를 저장할 2차원 배열을 만든다. 이때, 자기 자신으로 가는 경로는 (dist[I][J]에서 I===J일 경우) 0으로 초기화해준다. 음수 사이클을 검출하기 위해서다. 자기 자신을 경로로 갖는 사이클이 존재하고 그 경로가 계속해서 음수 가중치를 갖지 않는 한 자기 자신의 경로는 항상 0이 되어야 한다. 따라서, 탐색 후 dist[I][I]<0이면 해당 그래프는 음수 사이클을 갖고 있다고 판단이 가능하다. 

	A	B	C	D
A	0	3	INF	-4
B	3	0	INF	8
C	3	INF	0	INF
D	INF	INF	7	0

 

2. 경유지 정점을 설정한 후 경유지를 거쳐가는 경로의 비용이 더 적다면 갱신한다.

 경유지 정점을 먼저 설정한 후 👉 출발 정점과 도착 정점을 정한다. dist[출발정점][도착정점]와 dist[출발정점][경유지]+dist[경유지][도착정점]를 비교해 최단 거리로 갱신해 나간다.

 

 경유지 정점을 A로 설정, 출발 정점을 B, 도착 정점을 C로 정한다면.

dist[B][C](INF)와 dist[B][A]+dist[A][C](3+INF)를 비교, 갱신할 것이 없으므로 넘어간다.

 

 경유지 A, 출발 정점 B, 도착 정점 D 👉 dist[B][D](8)와 dist[B][A]+dist[A][D](3+(-4))를 비교, 경유지 A를 거친 거리가 더 최단 거리(-1)이므로 dist[B][D]를 갱신한다.

	A	B	C	D
A	0	3	INF	-4
B	3	0	INF	-1
C	3	INF	0	INF
D	INF	INF	7	0

경유지 A, 출발 정점 C, 도착 정점 B 👉 dist[C][B](INF)와 dist[C][A]+dist[A][B](3+3) 👉 dist[C][B]=6

	A	B	C	D
A	0	3	INF	-4
B	3	0	INF	-1
C	3	6	0	INF
D	INF	INF	7	0

 경유지 A, 출발 정점 C, 도착 정점 D 👉 dist[C][D](INF)와 dist[C][A]+dist[A][D](3+(-4)) 👉 dist[C][D]=-1

	A	B	C	D
A	0	3	INF	-4
B	3	0	INF	-1
C	3	6	0	-1
D	INF	INF	7	0

경유지 A, 출발 정점 D, 도착 정점 B 👉 dist[D][B](INF)와 dist[D][A]+dist[A][B](INF+3)

경유지 A, 출발 정점 D, 도착 정점 C 👉 dist[D][C](7)와 dist[D][A]+dist[A][C](INF+INF)

경유지 B, 출발 정점 A, 도착 정점 C 👉 dist[A][C](INF)와 dist[A][B]+dist[B][C](3+INF)

경유지 B, 출발 정점 A, 도착 정점 D 👉 dist[A][D](-4)와 dist[A][B]+dist[B][D](3+(-1))

경유지 B, 출발 정점 C, 도착 정점 A 👉 dist[C][A](3)와 dist[C][B]+dist[B][A](6+3)

경유지 B, 출발 정점 C, 도착 정점 D 👉 dist[C][D](-1)와 dist[C][B]+dist[B][D](6+(-1))

경유지 B, 출발 정점 D, 도착 정점 A 👉 dist[D][A](INF)와 dist[D][B]+dist[B][A](INF+3)

경유지 B, 출발 정점 D, 도착 정점 C 👉 dist[D][C](7)와 dist[D][B]+dist[B][C](INF+INF)

경유지 C, 출발 정점 A, 도착 정점 B 👉 ... 반복

 

3. 반복하며 탐색한다.

 모든 정점을 경유지로 정하고 출발 정점과 도착 정점을 바꿔가며 반복하며 탐색해간다. 이 과정에서 기존에 기록돼있던 거리보다 다른 경유지를 거쳐서 온 거리가 더 짧다면 기록해나간다. (다이나믹 프로그래밍) 

 기억해야 할 것은 경유지 먼저 정하고! 출발 정점 정하고! 도착 정점 정하는 것이다! (경출과 도둑 게임이라고 기억하면 쉽다.)

 

	A	B	C	D
A	0	3	3	-4
B	3	0	6	-1
C	3	6	0	-1
D	10	13	7	0

 최종 dist 배열은 위와 같이 만들어진다.

구현(JavaScript)

이 그래프의 모든 정점 - 모든 정점 사이의 최단거리를 구현해보자!

//input.txt
//첫번째 줄 : 정점의 개수, 간선의 개수
//두번째 줄 ~ : 간선 정보가 주어진다.(출발 정점, 도착 정점, 가중치)
4 6
1 2 3
1 4 -4
2 1 3
2 4 8
3 1 3
4 3 7

 정점과 간선의 정보를 받은 후 초기화를 먼저 진행해준다. (기본 이해의 1번) 자기 자신으로 가는 경로는 0으로, 간선이 있다면 그 가중치를, 경로가 존재하지 않는 다면 Infinity로 초기화를 해준다.

 const fs = require('fs');
  const input = fs.readFileSync('input.txt').toString().trim().split('\n');

  const [N, E] = input[0].trim().split(' ').map(Number);

  const dist = Array.from(Array(N), () => Array(N).fill(0));

  for (let i = 0; i < E; i++) {
    const [from, to, cost] = input[1 + i].trim().split(' ').map(Number);
    dist[from - 1][to - 1] = cost;
  }

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (i !== j) {
        if (!dist[i][j]) {
          dist[i][j] = Infinity;
        }
      }
    }
  }

 

다익스트라 부분은 위에서 언급했듯이 경유지(k)를 정하고 출발 정점(i)과 도착 정점(j)을 정해준다. 3중 for문으로 구현해준다. 

for (let k = 0; k < N; k++) {
    //경유지
    for (let i = 0; i < N; i++) {
      //출발 정점
      for (let j = 0; j < N; j++) {
        if (dist[i][k] === Infinity || dist[k][j] === Infinity) {
          continue;
        }

        //도착 정점
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }

최종 결과

 만약 dist[I][I]<0이 검출된다면 그 그래프는 음수 사이클을 갖고 있는 것이므로 최단 거리를 구할 수 없다. 

const main = (function () {
  const fs = require('fs');
  const input = fs.readFileSync('input.txt').toString().trim().split('\n');

  const [N, E] = input[0].trim().split(' ').map(Number);

  const dist = Array.from(Array(N), () => Array(N).fill(0));

  for (let i = 0; i < E; i++) {
    const [from, to, cost] = input[1 + i].trim().split(' ').map(Number);
    dist[from - 1][to - 1] = cost;
  }

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (i !== j) {
        if (!dist[i][j]) {
          dist[i][j] = Infinity;
        }
      }
    }
  }

  for (let k = 0; k < N; k++) {
    //경유지
    for (let i = 0; i < N; i++) {
      //출발 정점
      for (let j = 0; j < N; j++) {
        if (dist[i][k] === Infinity || dist[k][j] === Infinity) {
          continue;
        }

        //도착 정점
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }

  console.log(dist);
})();

그냥 다익스트라를 정점만큼 돌리면 안 되나요?

 가능하다. 다만, 다익스트라는 음수 가중치가 있을 때는 사용 자체가 불가능하다. 양수 가중치만 있을 경우, 보통 플로이드-워셜로 접근할 수 있는 문제는 복잡도가 올라갈 수는 있으나 다익스트라로도 접근할 수 있다. 출발 정점과 도착 정점을 바꿔가며 다익스트라를 실행시키면 되나 결국 모든 정점과 모든 정점 사이의 최단 거리를 구할 때는 시간 복잡도를 잘 고려해 플로이드-워셜로 풀어도 문제가 없다면 플로이드-워셜이 구현도 더 쉬운 편이고 깔끔해 보인다.

시간 복잡도

$$O(N^3)$$

 구현은 쉽지만 정점의 개수 N만큼 3번 돌기 때문에 시간 복잡도가 매우 높다. 따라서 정점의 개수를 잘 보고 플로이드-워셜 알고리즘을 적용해야 한다.