[DP] Floyd-Warshall

이 알고리즘은 Floyd-Warshall 알고리즘이라고 불리기도 하고, 줄여서 floyd 알고리즘이라고 불리기도 한다.

 

이 알고리즘도 다익스트라와 비슷하게, 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로를 찾는 것이다.

 

하지만 다익스트라와는 다르게 가중치가 음의 값을 가지고 있어도 되고, 모든 쌍의 최단경로를 구하는 알고리즘이기 때문에 계산이 끝난 후에는 내 마음대로 출발점과 끝나는 점을 잡아도 최소 거리를 알려준다.

 

이 알고리즘은 점화식을 통해 계산을 하는데,  간단하게 생각해야 이해하기 쉽다.

1) 출발지에서 경유지를 거쳐, 도착지 까지 간다.

2) 출발지에서 도착지로 바로 가는 경우와 출발지에서 경유지를 거쳐 도착지로 가는 경우 중 더 빠른 길을 담아둔다.

이 두 동작만 반복하면 된다. 

하지만 시간 복잡도가  O(N^3) 이기 때문에, 정점이 많다면 사용할 수 없다.

또, 모든 점이 이어져 있는지는 알 수 없다. 어떻게 갔는지 경로도 알 수 없다.

그냥 A부터 B까지 가는 최소 비용을 알려줄 뿐이다. 

 

public class Floyd { //모든 쌍의 최단 경로 구하기! 다익스트라는 가중치 음수 안되는데 얘는 가능.
	//N이 크지 않을 때 사용 가능. N이 100보다 작을 때! O(N^3)이라서..
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[][] D = new int[N][N];
		
		
		for(int k=0; k<N; k++) { //경유지
			for(int i=0; i<N; i++) { //출발지
				for(int j=0; j<N; j++) {//도착지
					//모든 점에서 k를 거쳐가는 최단 비용을 계산해봄.
					D[i][j] = Math.min(D[i][k]+D[k][j], D[i][j]);
				}
			}
		}
	}
}

 

그렇지만 코드가 쉽고 직관적이라 N이 작을 때 완탐이 필요하면 아주 유용한 알고리즘 인 것 같다.