[JAVA] 최단거리 - (DP)플로이드 워샬

🔎 플로이드 워샬 알고리즘이란?

모든 지점에서 다른 모든 지점까지의 최단경로를 모두 구해야할 때 사용하는 알고리즘이다. 중간 정점을 차례대로 추가하면서 최단 경로가 점진적으로 더 짧은 값으로 갱신하고, 소스코드가 다익스트라에 비해 매우 짧아 구현이 쉽다.

🔧 플로이드 워샬 알고리즘 구현하기

점화식

STEP 0. 최단 거리 테이블을 자기자신 → 자기자신 경우를 제외하고 무한으로 채운다.

for(int i=0; i<graph.length; i++) {
		for(int j=0; j<graph.length; j++) {
			// 자기자신 → 자기자신 : 0
			if(i==j) continue;
			graph[i][j] =  INF;
		}

STEP 1. 입력을 받는다. 연결된 정점의 경우 최단 거리 테이블에 값을 갱신한다.

for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			//1. 시작점
			int v = Integer.parseInt(st.nextToken());
			//2. 끝점
			int w = Integer.parseInt(st.nextToken());
			//3. 가중치
			int cost = Integer.parseInt(st.nextToken());
			graph[v][w] = cost;
		}

STEP 2. 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]);
				}
			}
		}	

전체 코드

import java.io.*;
import java.util.*;

public class FloydWarshalTest {
	
	static final int INF = 1000000000;
	
	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();
		}
		
	}
	
	public static void main(String args []) throws IOException{
		
		//입력받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//1. 정점의 갯수 받기
		int N = Integer.parseInt(br.readLine());
		//2. 간선의 갯수 받기
		int M = Integer.parseInt(br.readLine());
		
		int[][] graph  = new int[N+1][N+1];
		
		for(int i=0; i<graph.length; i++) {
			for(int j=0; j<graph.length; j++) {
				// 그니까 나 → 나로 가는 것은 0이니까 얘를 제외하고!!!
				if(i==j) continue;
				graph[i][j] =  INF;
			}
		}
		
		StringTokenizer st;
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			//1. 시작점
			int v = Integer.parseInt(st.nextToken());
			//2. 끝점
			int w = Integer.parseInt(st.nextToken());
			//3. 가중치
			int cost = Integer.parseInt(st.nextToken());
			graph[v][w] = cost;
		}
		
		System.out.println(INF);
		floyd(graph,N);
	}

}

입력
5
9
1 2 10
1 3 5
2 3 2
3 1 1
3 2 13
4 1 8
4 5 3
5 4 9
5 2 31

출력 결과
0 10 5 0 0
3 0 2 0 0
1 11 0 0 0
8 18 13 0 3
17 27 22 9 0

🤔 다익스트라 VS 플로이드 워샬

구분	다익스트라	플로이드 워샬
목적	한 정점에서 다른 모든 정점까지의 최단경로를 찾는 알고리즘	모든 정점 쌍 사이의 최단 경로를 구하는 알고리즘
시간복잡도	O(E + V log V)	O(V³)
특징	가중치가 양수인 그래프에만 적용된다.	음수 가중치가 포함된 그래프에서도 동작한다. 그러나 그래프에 음수 사이클이 있는 경우 제대로 된 값을 찾지 못할 수도 있다.
사용예시	지도 애플리케이션에서 한 장소에서 다른 장소까지의 최단 경로 탐색	네트워크 상에서 모든 노드 간의 최단 통신 경로를 계산하는 경우

• 다익스트라의 경우 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 이후 해당 노드를 거쳐가는 경로를 확인하며 최단 거리 테이블을 갱신하는 방식으로 동작한다.
• 플로이드 워셜 알고리즘 또한 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만, 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다.

사진 출처 : https://freedeveloper.tistory.com/277?category=888096