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

플로이드-와샬 알고리즘이란 ?

• 그래프의 최단 경로를 구하는 알고리즘

• 모든 정점에서 모든 정점까지 최단 거리를 구함.

• 음수 사이클 없어야 함. (음수 가중치는 허용)

• 인접 행렬로 표현한 그래프의 시간복잡도 : O(N^3)

• DP 사용

다익스트라 가 한 정점에서 출발해서 다른 모든 정점으로의 최단 경로라면,
플로이드-와샬 은 모든 정점에서 출발해서 다른 모든 정점으로의 최단 경로를 구함.

원리

경유지를 k, 출발 정점을 i, 도착 정점을 j 라고 하자.
그래프는 graph 라는 2차원 배열에 저장돼있다.

graph[i][k] + graph[k][j] 는 i 에서 j 까지 가는데 k 를 거쳐서 가는 거리이다.
만약, graph[i][j] > graph[i][k] + graph[k][j] 라면 i 부터 j 까지 가는데 k 를 거쳐서 가는 것이 더 최단 거리라는 의미이므로 graph[i][j] = graph[i][k] + graph[k][j] 으로 갱신해준다 !

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

예시

1) 1번 정점 경유

• graph[3][2] = 11 로 변경
• graph[4][2] = 18 로 변경
• graph[4][3] = 13 으로 변경

2) 2번 정점 경유

• graph[5][3] = 33 으로 변경

이런식으로 5번 정점까지 모두 경유해서 갱신하면 최종 결과는 다음과 같다.

코드

주요 코드

 public static void floyd(int[][] graph, int n) {
		// 경유지
		for (int k = 1; k <= n; k++) {
			// 출발지
			for (int i = 1; i <= n; i++) {
				// 도착지
				for (int j = 1; j <= n; j++) {
					graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
				}
			}
		}

전체 코드

public class Main {
	static final int INF = 1000000000;
	
	public static void main(String[] args) throws IOException {
		// 그래프 입력 받기
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(bf.readLine()); // 정점 개수
		int m = Integer.parseInt(bf.readLine()); // 간선 개수
		int[][] graph = new int[n + 1][n + 1];
		
		for (int i = 1; i < graph.length; i++) {
			for (int j = 1; j < graph.length; j++) {
				if(i == j) continue;
				graph[i][j] = INF;
			}
		}

		StringTokenizer st;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int v = Integer.parseInt(st.nextToken()); // 출발 정점
			int w = Integer.parseInt(st.nextToken()); // 도착 정점
			int cost = Integer.parseInt(st.nextToken()); // 가중치
			
			graph[v][w] = cost;
		}
		
		//플로이드 알고리즘 수행
		floyd(graph, n);
	}
    
    public static void floyd(int[][] graph, int n) {
		// 경유지
		for (int k = 1; k <= n; k++) {
			// 출발지
			for (int i = 1; i <= n; i++) {
				// 도착지
				for (int j = 1; j <= n; j++) {
					graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
				}
			}
		}
		
		// 출력
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (graph[i][j] == INF) System.out.print(0 + " ");
				else System.out.print(graph[i][j] + " ");
			}
			System.out.println();
		}
	}

}

💡 참고
https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%99%80%EC%83%ACFloyd-Warshall-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98