Floyd-Warshall

Floyd-Warshall : 그래프의 최단거리 알고리즘

플로이드 워셜(Floyd-Warshall)

• 그래프에서 최단 거리를 구하는 알고리즘

• 기능 : 모든 노드 간에 최단 경로 탐색

• 특징 : 음수 가중치 에지가 있어도 수행이 가능하다.

  • 노드의 갯수가 적을 때 사용해볼만 함

• 시간 복잡도 : O(N^3)

특징

A → B 노드까지 최단 경로를 구했다고 가정하고 최단 경로 위에 C노드가 존재한다면 부분 경로 역시 최단 거리이다.

• 코드의 길이가 매우 짧고, 3중 for문으로 구성되어 있다.

• 노드의 갯수가 적기 때문에 인접 행렬로 최단거리 그래프를 만들 수 있다.

• 점화식 : D[S][T] = Math.min(D[S][T], D[S][K] + D[K][T]

  • K : 거쳐가는 정점

  • if (D[S][T] > D[S][K] + D[K][E]) D[S][T] = D[S][K] + D[K][T]

• S -> T 까지 최단 경로가 존재한다. 이 경로 사이에 존재하는 모든 K를 탐색하는 것이다. (브루트포스처럼)

• 갈 수 있는 모든 K를 탐색해 보고 그중 값이 가장 작은 K를 선택

구현 방법

1. 인접 행렬 생성

• i 는 출발 노드, j 는 도착 노드, k는 경유 노드, 가중치는 w

  • (i == j) D[i][j] = 0

  • (i ≠ j) D[i][j] = INF

  • D[i][j] = w

1. 점화식으로 그래프 업데이트

for 거쳐가는 모든 K (0 ~ N) // N = 노드 갯수
	for 출발 노드 i  (0 ~ N)
		for 도착 노드 j (0 ~N)
			if (D[i][j] > D[i][k] + D[k][j]) D[i][j] = D[i][k] + D[k][j];
			OR
			D[i][j] = Math.min(D[i][j], D[i][k] + D[k][j]);

// 갈 수 없는 곳(INF 값을 가지고있는)은 다시 0으로 초기화

• 최종 그래프에서 값이 무한대(INF)는 절대 갈 수 없는 경로를 의미한다.

문제 :

• BOJ 11403 경로 찾기 : https://www.acmicpc.net/problem/11403

• BOJ 11404 플로이드 : https://www.acmicpc.net/problem/11404

• BOJ 2060 바이러스 : https://www.acmicpc.net/problem/2606

• BOJ 14938 서강 그라운드 : https://www.acmicpc.net/problem/14938