티스토리 뷰
플로이드 워셜(Floyd Warshall) 알고리즘은 동적 계획법으로 모든 최단 경로를 구하는 알고리즘이다.
먼저 초기화를 해줘야 하는데 최단경로가 있으면 최단경로를 없으면 최댓값을 넣어주어야 한다.
그래야 최단경로를 구할 수 있다.
3중 for 문으로 동작하는데 첫 for 문부터 각각 거쳐 가는 점, 출발하는 점, 도착하는 점을 나타낸다.
아래 코드는 초기화를 했다는 가정하에 작성했다.
class Floyd{
int len = 10;
int[][] arr = new int[len][len];
void floyd(){
for(int i = 0; i < len; i++){ // 거쳐가는 점
for(int j = 0; j < len; j++){ // 출발하는 점
if(i == j){
continue;
}
for(int k = 0; k < len; k++){ // 도착하는 점
if(i == k){
continue;
}
if(j != k){
if(arr[j][k] > arr[j][i] + arr[i][k]){
arr[j][k] = arr[j][i] + arr[i][k];
}
}
}
}
}
}
}
두 가지의 경우 그냥 지나가면 된다.
1. j와 k가 같을 때 : 자기 자신을 가리킬 때
2. i가 j나 k와 같을 때 : 거치는 점이 출발하는 점이나 도착하는 점과 같을 때
코드를 보면 j에서 k로 갈 때 바로 가는 것보다 i를 거쳐서 가는 게 더 빠를 경우 j에서 k로 가는 최단경로를 수정하게 된다.