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

Jay·2021년 4월 12일
0

알고리즘-Concept

목록 보기
9/15
post-thumbnail

플로이드 와샬 !?

  • 플로이드 와샬모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘 이다.
  • 다익스트라(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();
		}
		
	}
}

아주 기본적인 문제를 BOJ에서 풀어보자. 적용을 위해!

BOJ 11404 - 플로이드

profile
developer

0개의 댓글