최단 경로 알고리즘 : 플로이드-워셜(Floyd-Warshall)

개요

• 모든 노드에서 모든 노드까지의 최단 경로를 계산하는 알고리즘이다.
• 알고리즘을 한 번 실행함으로써 모든 노드 간 최단 경로를 계산할 수 있다.
• 노드 간 거리를 저장하기 위해서 행렬을 사용한다.
• 행렬의 초깃값은 그래프의 인접 행렬과 같다.
• 매 라운드마다 각 경로에서 중간 노드로 사용할 노드를 선택하여 거리를 줄여나간다.

구현

• 3중 반복문으로 쉽게 구현할 수 있다.
• 가장 바깥쪽은 중간 노드이고, 2번째, 3번째는 경로를 계산할 대상 노드이다.
• 각 반복문은 그래프의 노드 개수만큼 수행되므로, 노드 개수 n에 대하여 시간복잡도는 O(n^3)이다.

Java

int INF = 무한, 알고리즘 구현 상 도출될 수 없는 큰 값으로 선언함.
int [] [] adj;
int [] [] dist;

...

void floydWarshall() {
  for(int i = 1; i <= n; i++) {
    fori(int j = 1;  j <= n; j++) {
      if(i == j) {
      	dist [i] [j] = 0;
      } else if(adj [i] [j] != 0) {
      	dist [i] [j] = adj [i] [j];
      } else {
      	dist [i] [j] = INF;
      }
	}	
  }
  
  for(int i = 1; i <= n; i++) {
  	for(int j = 1; j <= n; j++) {
      for(int k = 1; k <= n; k++) {
      	if(dist [j] [k] > dist [j] [i] + dist [i] [k]) {
			dist [j] [k] = dist [j] [i] + dist [i] [k];
      	}
      }
    }
  }
}