[알고리즘] 플로이드-와샬 알고리즘

[알고리즘] 플로이드 와샬 알고리즘

* 플로이드 와샬 알고리즘이란?

 - 그래프에서 모든 꼭지점 사이의 최단 경로의 거리를 구하는 알고리즘이다.

 - 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다.

 - 3중 for문 중 제일 바깥쪽 반복문은 겨쳐가는 꼭지점이다. 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점

 - 시간 복잡도는 3중 for문으로 인한 O(n^3) 이다.

 - 다익스트라, 벨만 포드 알고리즘은 하나의 시작점에 대해 최단 경로를 찾아주지만

   플로이드 워셜 알고리즘은 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 다 구해준다.

 - 많은 시간이 소요되지만 이 알고리즘을 이용해 해결해야 할 상황도 존재하므로 중요!

(참조 : 위키백과, http://www.crocus.co.kr/536)

* 코드

 - 한마디로 a, b, c, d의 점에서 a->b로 가는 최단 거리를 비교하고 넣어주는 것이다. a->b로 가는 길은 a->b도 있고 a->c->b도 있을 수 있다. (a->c->b의 선이 있다는 가정 하에)

 - 쉽게 이해가 가지 않아서 그림으로 잘 표현된 블로그(http://www.crocus.co.kr/536)를 통해 이해하였다. 

for (int k = 0; k < N; ++k) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (d[i][j] > d[i][k] + d[k][j]) {
                d[i][j] = d[i][k] + d[k][j];
            }
        }
    }
}

 - 관련 문제를 풀어보았다 (케빈 베이컨의 6단계 법칙 : https://www.acmicpc.net/problem/1389)