Floyd 알고리즘

최단경로 구하는 그래프이론에 쓰이는 알고리즘이다.

포문을 삼중으로 돌려

A에서 B로 가는데 C를 거치는 경로가 더 작다면 arr[A][C] > arr[A][B] + arr[B][C], 값을 작은 값으로 갱신하는 방식이다.

모든 경우의 수를 다 돌려서 가장 작은 값들로 리셋 시키는 방식, 시간복잡도는 O(n^3)이다.

int i, j, k;

for(j = 0; j < n; j++){
for(i = 0; i < n; i++){
for(k = 0; k < n; k++){
if(dist[i][k] > dist[i][j] + dist[j][k])
dist[i][k] = dist[i][j] + dist[j][k];
}
}
} 

for문을 구성할 때 거치는 C를 최상위 for문으로 배치한다. 간단해 보이는 코드이면서도 간단하게 문제가 해결 가능한 훌륭한 코드이다.

항상 볼 때마다 나중에 써야지 하면서도 막상 쓰려고 하면 잘 못쓰겠는 알고리즘..