플로이드 워셜 알고리즘

1) 개념

- 모든 최단 경로를 구하는 알고리즘

- 다익스트라가 하나의 정점에서 모든 정점까지의 최단거리를 구한다면, 플로이드-워셜 알고리즘은 한번 실행하여 모든 노드간 최단 경로를 구할 수 있다. 다익스트라에 대한 설명은 아래 링크를 통해 확인하자.

2023.07.05 - [Learning-log -CS/Data Structure & Algorithm] - (알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교)\

(알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교)

 

- 음의 간선도 사용 가능하다.

- 시간복잡도가 O(n^3)이므로 그래프의 크기가 작은 경우만 적용 가능하다.

 

2) 알고리즘 과정

- 여러 라운드로 구성되며 각 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드 선택하고 더 짧은 길이를 선택하여 줄이는 과정 반복한다.

- 노드의 개수가 V라면 총 V번의 라운드를 거치게 된다.

- 모든 노드들을 중간노드로 선정하는 과정을 각 라운드마다 거치게 된다. i번 라운드는 i-1노드가 중간노드가 되는 과정을 계산하는 것이다.

 

간략한 과정은 아래와 같다.

 

adj : 2차원 인접행렬, 경로가 없는 경우 INF 값이 들어있음

dist : 최단거리 2차원 배열

 

① dist 세팅

② 총 3중 for 문 구현

 

    ② - (1) 1번째 for문(제일 바깥, 변수 : k) : 각 라운드를 의미하는 for문.  k번째 노드를 중간 노드로 넣는 과정

    ② - (2) 2번째 for문(중간, 변수 : i) / 3번째 for문(제일 안쪽, 변수 j) : i번째와 j번째를 연결하는 거리와 i-k-j를 연결하는 거리의 대소관계를 비교하여, 더 작은 값으로 dist 배열 갱신

 

그럼 다익스트라처럼 아래 예시를 두고 dist 배열의 갱신과정을 자세히 살펴보자. 

 

 

① dist 기본적으로 간선이 연결된 경우 가중치 값을, 연결된 값이 없는 경우 INF 값을 넣어준다. 

위 예시를 바탕으로 준비된 dist 배열은 아래와 같다.

 

 

② k( k=1, 2, 3, .. V)번째 노드를 거쳐갈 때의 dist 값을 갱신해준다. 

따라서 X번 → Y번 노드로 이동할 때 소요되는 비용과 X → 1 → Y 순으로 이동할 때 소요되는 비용을 비교하여 더 작은 값을 dist 배열을 갱신하는 것이다.

 

▶ k=1 일때, 1번 노드를 거쳐가는 경우를 고려하므로 1행은 제외하고 dist 값을 갱신한다.

• ( 2 →  4 )  vs ( 2 → 1 → 4 ) 
  • min (dist[2][4], dist[2][1]+dist[1][4] ) = min( INF, INF) = INF
• ( 3 → 4 ) vs ( 3 → 1 → 4 )
  • min (dist[3][4], dist[3][1]+dist[1][4] ) = min( 5, 1+INF) = 5
  • dist[3][4]와 dist[3][1]+dist[1][4]를 비교하여 각각 5와 INF가 되므로 dist[3][4] 값이 유지된다.

• ( 4 →  2 )  vs ( 4 → 1 → 2 ) 
  • min (dist[4][2], dist[4][1]+dist[1][2] ) = min( INF, 6 + 1) = 7

 

위와 같은 과정을 k=1부터 5까지 위 과정을 수행한다면 dist 배열은 아래와 같이 갱신된다.

 

이렇게 모든 노드를 거치는 상황을 계산하면 모든 점에서 모든 점으로 가는 최소 거리를 계산할 수 있다.

 

3) 코드 구현

그럼 이제 이를 일반적인 상황에 적용한 코드를 살펴보자.

public class FloydWarshall {
	public static void main(String[] args) throws NumberFormatException, IOExceaption{

//입력받기(인접행렬 방식) 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int V = Integer.parseInt(br.readLine());
		Stringtokenizer st = new Stringtokenizer(br.readLine());
	
		int[][] adjMatrix = new int[V][V];
		for(int i=0; i<V; i++) { 
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<V; j++){
					adjMatrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}

//거리배열 값 채우기
		final int Inf = Integer.MAX_VALUE;
		for(int i=0; i<V; i++){
        	for(int j=0; j<V; j++){
            	if(i==j) dist[i][j] = 0;
                else if(adjMatrix[i][j]==0) dist[i][j] = Inf;
                else dist[i][j] = adjMatrix[i][j];
             }
        }



//플로이드 워셜 알고리즘 수행(3중 for문으로 점화식 적용)

	for(int k=0; k<V; k++){
    	for(int i=0; i<V; i++){
        	for(int j=0; j<V; j++){
            	dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j])
            }
        }
    }
    
 }

 

 

4) 관련 문제

https://www.acmicpc.net/problem/17182

17182번: 우주 탐사선