Floyd-Warshall algorithm

그래프에서 최단 거리를 구하는 알고리즘이다. 단, 특정 노드가 아닌 모든 노드 간에 최단 경로를 탐색한다. 

음수 가중치가 있어도 가능하다.

동적 계획법의 원리를 이용해 알고리즘에 접근한다.

시간 복잡도는 O(V^3)이다. -> 시간 초과때문에 규모가 작은 경우에 활용한다(N = 200 정도?). 

🔰구현

삼중 for문으로 되어 있고, 구현이 쉽다.

a 노드에서 b 노드까지 최단 경로를 구했다고 가정했을 때, 그 경로를 이루는 부분 경로 역시 최단 경로다. 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로 조합으로 이뤄진다.

D[S][E] = min(D[S][E], D[S][K] + D[K][E]),  K는 S 노드와 E 노드까지의 경로에 존재하는 모든 노드를 의미한다.

1. 최단 거리 인접 행렬을 선언하고 초기화한다. 출발 노드와 도착 노드가 같으면 0, 나머지 칸은 무한대로 초기화한다.
2. 최단 거리 인접 행렬에 그래프 데이터를 저장한다. D[S][E] = W
3. 최단 거리 인접 행렬을 업데이트 한다. -> K, S, E 순으로 3중 루프를 돌린다.

for 경유 노드 K에 관해 (1 ~ N):
    for 출발 노드 S에 관해 (1 ~ N):
        for 도착 노드 E에 관해 (1 ~ N):
            D[S][E] = min(D[S][E], D[S][K] + D[K][E])

결과적으로 최단 거리 인접 행렬이 모든 노드 쌍에 관한 최단 거리를 표현한다.