[알고리즘] 모든 정점 사이 최단경로 구하기 - 플로이드 알고리즘 (백준 11404 - Java)

플로이드 알고리즘

가중치가 주어진 그래프에서 모든 정점 사이의 최단경로를 구할 때

사이클이 존재하지 않고, 가중치가 음이거나 양인 경우 플로이드 알고리즘을 사용할 수 있다.

 

위키백과 : 플로이드-워셜 알고리즘

 

1. 경유지 k와 두 점 i,j 선택
2. 두점 사이 이동 시 i -> j 보다 k를 경유해서 가는 것이 더 빠르다면 최솟값 갱신
3. 모든 경우에 대해 반복

 

모든 경유지에 대한 정점 사이의 최단 경로를 전부 확인하므로

O(V^3) (V는 정점)

의 시간복잡도를 갖는다.

 

예제 코드 (백준 11404)

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

11404번: 플로이드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// [백준] 11404. 플로이드 (Java)
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine()); // 도시의 개수
		int m = Integer.parseInt(br.readLine()); // 버스의 개수
		
		int[][] city = new int[n + 1][n + 1];
		
		for(int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());

			if(value < city[start][end] || city[start][end] == 0) {
				city[start][end] = value;
			}
		}
		
        // k = 경유지
		for(int k = 1; k <= n; k++) {
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= n; j++) {
					if(i == j) continue;
					
                    // i -> j 를 이동하는데 k를 경유할 수 있다면
					if(city[i][k] > 0 && city[k][j] > 0){              
                        // k를 경유해서 이동하는 경우가 더 빠르다면 최솟값 갱신
						if((city[i][k] + city[k][j] < city[i][j]) ||
								city[i][j] == 0) {
							city[i][j] = city[i][k] + city[k][j];
						}
					}
				}
			}
		}
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				System.out.print(city[i][j] + " ");
			}
			System.out.println();
		}
	}
}