다익스트라는 그리디 기법을 기반으로 수행
플로이드 와샬은 다이나믹 프로그래밍 기반으로 수행
위에서 말했듯,
삼중 반복문 실행
1. 첫번째 반복문 i = 1 ~ N : 거쳐가는 정점
2. 두번째 반복문 j = 1 ~ N : 시작점
3. 세번째 반복문 k = 1 ~ N : 도착점
dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])
즉, i 에서 j 로 갈 때, k를 거쳐가는 것이 더 가깝다면 대입
public class floydwarshall {
static int INF = 999999;
public static void main(String[] args) {
int arr[][] = {{0, 1, INF, 4, 5},
{INF, 0, 3, 2, 1},
{1, INF, 0, 5, 3},
{INF, INF, 4, 0, 2},
{4, INF, 1, 7, 0}};
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr.length; j++) {
for(int k=0; k<arr.length; k++) {
if(arr[j][k] > arr[j][i] + arr[i][k])
arr[j][k] = arr[j][i] + arr[i][k];
}
}
}
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr.length; j++) {
System.out.print(arr[i][j]+ " ");
}System.out.println();
}
}
}
아주 기본적인 문제를 BOJ에서 풀어보자. 적용을 위해!