[알고리즘] 플로이드 와샬 (Floyd-Warshall) 알고리즘

Jay·2021년 4월 12일

알고리즘-Concept

목록 보기

9/15

플로이드 와샬 !?

플로이드 와샬은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘 이다.
다익스트라(Dijkstra) 알고리즘은 어떠한 정점을 기준으로 잡고 다른 모든 정점으로의 최단 거리를 구하는 알고리즘이다.

특징

다익스트라는 가장 적은 비용을 가지는 간선을 하나씩 선택하여 알고리즘을 수행했다면,
플로이드 와샬은 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 특징이 있다.

다익스트라는 그리디 기법을 기반으로 수행
플로이드 와샬은 다이나믹 프로그래밍 기반으로 수행

위에서 말했듯,

플로이드-와샬 알고리즘은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다.

음수 가중치를 갖는 간선도 순환만 없다면 처리가 가능하다.
제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세번째 반복문은 도착하는 꼭짓점이다.

시간복잡도

반복문을 3개를 중첩하기에.. 시간 복잡도는 O(V^3)로 복잡하다.
그래서 N의 크기가 상대적으로 적을 때 사용해야 한다.

핵심 풀이

삼중 반복문 실행
1. 첫번째 반복문 i = 1 ~ N : 거쳐가는 정점
2. 두번째 반복문 j = 1 ~ N : 시작점
3. 세번째 반복문 k = 1 ~ N : 도착점

dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

즉, i 에서 j 로 갈 때, k를 거쳐가는 것이 더 가깝다면 대입

코드

public class floydwarshall {
	static int INF = 999999;
	public static void main(String[] args) {
		
		int arr[][] = {{0,   1,   INF, 4, 5},
                       {INF, 0,   3,   2, 1},
                       {1,   INF, 0,   5, 3},
                       {INF, INF, 4, 0, 2},
                       {4, INF, 1, 7, 0}};
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr.length; j++) {
				for(int k=0; k<arr.length; k++) {
					if(arr[j][k] > arr[j][i] + arr[i][k])
						arr[j][k] = arr[j][i] + arr[i][k];
				}
			}
		}
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr.length; j++) {
				System.out.print(arr[i][j]+ " ");
			}System.out.println();
		}
		
	}
}