Floyd-Warshall Shortest Path Algorithm

00. 사전 지식

  • 최단 경로 알고리즘 : 가장 짧은 경로를 찾는 알고리즘
  • 다이나믹 프로그래밍 (Dynamic Programming)
    • 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
    • 작은 문제에 대한 해답과 점화식을 활용해서 더 큰 문제를 해결하는 방법
  • 경유점 개념
    • 두 정점 u, v 를 잇는 어떤 경로가 있을 때, 이 경로는 항상 시작점 u 와 끝점 v 를 지남
    • 이 외에 이 경로는 다른 정점들을 지나쳐 갈 수도 있음

01. 정의

  • 그래프에 존재하는 모든 정점 사이의 최단 경로를 한 번에 모두 찾아주는 알고리즘이다.
  • 플로이드 워셜 알고리즘은 다이나믹 프로그래밍으로 분류된다. 노드의 개수가 N 개일 때, N 번 만큼의 단계를 반복하여 “점화식에 맞게” 2 차원 리스트를 갱신하기 때문이다.
  • 2 차원 배열을 이용해서 3 중 반복을 하는 루프로 구성되어 있다.

02. 동작 방식

  • D(k) 배열 : 2 차원 배열, 0 부터 k 까지의 정점만을 이용했을 때, 두 정점 사이의 최단 경로를 기록하는 배열
    • D(k)[i][j] : 0 부터 k 까지의 정점만을 이용했을 때, 정점 i 에서 정점 j 까지의 최단 경로
    • 우리가 원하는 해답은 D(n-1)[i][j] 로 0 부터 n - 1까지의 모든 정점을 이용한 최단 경로
      • 정점 i 에서 정점 i 로 가는 경로는 0 으로 초기화
      • 정점 i 에서 정점 j 로 가는 경로가 없을 경우 INF(무한대) 로 초기화
  • 점화식 : D(k)[i][j] = Math.min(D(k-1)[i][j] , D(k-1)[i][k] + D(k-1)[k][j])
    • 수학적 귀납법과 유사하게 생각해서, D(k-1) 까지는 완벽한 최단 거리가 구해져있다고 가정
    • k 번째 정점을 추가로 고려할 때, 0 부터 k 까지의 정점만을 사용하여 정점 i 에서 정점 j 로 가는 최단 경로는 2 가지로 나누어볼 수 있다.
      1. 정점 k 를 거쳐서 가지 않는 경우
        • D(k)[i][j] 는 k 보다 큰 정점은 통과하지 않으므로, 이 경우 최단 거리는 D(k-1)[i][j] 가 된다.
      2. 정점 k 를 거쳐서 가는 경우
        • 이 경우 i 에서 k 까지의 최단 거리 D(k-1)[i][k] 에다가 k 에서 j 까지의 최단 거리인 D(k-1)[k][j] 를 더한 값이 된다.
    • 최종적인 최단 거리는 두 경로 중 더 짧은 경로가 될 것이다.
    • 이는 정점 k 를 경유하는 것이 보다 좋은 경로이면, 그 경로를 선택하고 아니면, 기존의 경로를 유지하겠다는 의미이기도 하다.
  • 기존에 주어진 그래프 정보로 초기값을 설정하고, 점화식을 이용해서 D(k) 배열을 채워가는 방식으로 동작한다. (like. Dynamic Programming)

03. 동작 방식 부연 설명

  • 핵심은 D(0) ⇒ D(1) ⇒ D(2) ⇒ … ⇒ D(n - 1) 순으로 최단 거리를 구하는 것이다.
  • 따라서, 각 단계에서는 해당 노드를 이용하는 것을 고려한다.
    • 예를 들어 3 번 노드를 이용하는 것을 고려할 때, 3 번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하면 된다. 정확하게는 A ⇒ 3 ⇒ B 를 고려한다.
    • 현재 D[A][B] = 3 일 때, D[A][3] + D[3][B] 가 2 라면, D[A][B] 는 2 로 갱신하는 것이다.
  • 따라서, 알고리즘에서는 현재 확인하고 있는 노드를 제외하고, n - 1 개의 노드 중에서 서로 다른 노드 (A, B) 쌍을 선택하고 최단 거리를 갱신한다.
    • 서로 다른 노드 (A, B) 쌍의 개수는 n - 1 개에서 2 개를 순열하는 것으로 대략 n ^ 2 라고 볼 수 있다.
    • n 개의 정점 모두 n ^ 2 개의 경우를 고려해야 해서 3 중 반복문이 나오게 되고, 시간복잡도가 O(n ^ 3) 이 된다.
  • 위의 동작 방식대로 라면 D[k][i][j] 와 같이 3 차원 배열이여야 할 것 같지만, 그럴 필요가 없다.
    • 왜냐하면, D[k][i][j] 를 구하기 위해서는 바로 전 단계 값인 D[k-1][i][j] 만 필요하기 때문이다.
    • 그리고 우리는 D[n-1][i][j] 의 값만 필요하고, 이는 각 단계마다 해당 노드를 추가로 고려하는 방식을 이용하면 D[i][j] 로도 0 ~ n - 1 개의 정점을 모두 고려할 수 있기 때문이다.

04. 동작 과정 설명

  1. 자기 자신에서 자기 자신으로 가는 비용은 0 으로 초기화
  2. 그래프 정보를 이용해서 각 간선의 비용 초기화

  3. 점화식에 따라 플로이드 워셜 알고리즘 수행

    Floyd-Warshall 알고리즘 동작 과정1 Floyd-Warshall 알고리즘 동작 과정2 Floyd-Warshall 알고리즘 동작 과정3

05. 구현

  • 언어 : JavaScript
// 위의 그림과 같은 그래프가 주어진다고 가정한다.
// 입력 정보 : 정점의 개수, 간선 정보

// 정점의 개수
const v = 4;

// 간선 정보 [시작 정점, 도착 정점, 가중치]
const edges = [
	[0, 1, 7],
	[0, 2, 5],
	[0, 3, 6],
	[1, 0, 3],
	[1, 2, 4],
	[2, 0, 2],
	[3, 2, 9],
];

const INF = Number.MAX_SAFE_INTEGER;

const FloydWarshallAlg = (v, edges) => {
	const dist = Array.from(Array(v), () => Array(v).fill(INF));

	// 1. 자기 자신에서 자기 자신으로 가는 비용은 0 으로 초기화
	for (let i = 0; i < v; i++) {
		dist[i][i] = 0;
	}

	// 2. 그래프 정보를 이용해 각 간선의 비용 초기화
	for (let i = 0; i < edges.length; i++) {
		const [from, to, weight] = edges[i];

		dist[from][to] = weight;
	}

	// 3. 점화식에 따라 플로이드 워셜 알고리즘 수행
	for (let k = 0; k < v; k++) {
		for (let i = 0; i < v; i++) {
			for (let j = 0; j < v; j++) {
				dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	return dist.map((v) => v.join(" ")).join("\n");
};

const distance = FloydWarshallAlg(v, edges);
console.log(distance);
// 0 7 5 6
// 3 0 4 9
// 2 9 0 8
// 11 19 9 0

06. 시간복잡도

  • Floyd-Warshall 알고리즘은 3 중 반복문으로 이루어져있으므로 시간복잡도는 O(N ^ 3) 이다.
  • Dijkstra 알고리즘을 n 번 돌리는 방법과 비교하면 큰 차이는 없지만, Floyd-Warshall 알고리즘은 매우 간결한 반복 구문을 사용하므로 Dijkstra 알고리즘 보다 상당히 빠르게 모든 정점 간의 최단 경로를 찾을 수 있다.

07. 출처

  • C언어로 쉽게 풀어쓴 자료구조 (천인국, 공용해, 하상호 지음)
  • 알고리즘 문제 해결 전략 2 (구종만 저자)
  • 이것이 코딩테스트다 (나동빈 지음)