[알고리즘] 플로이드-워셜 (Floyd-Washall)

플로이드 워셜이란?

모든 노드 사이의 최단 거리를 구하는 알고리즘이며, 음의 가중치에도 사용할 수 있습니다. 시간 복잡도는 O(V^3)으로 그래프의 크기가 작을 때만 사용할 수 있습니다.

 

어떻게 동작하나?

어떤 임의의 두 노드를 연결하기 위해, 중간 노드를 하나씩 포함시킨 거리와 비교하여 업데이트를 하는 방식입니다.

임의 두 노드(s, e) 사이의 최단거리를 d[s][e]라고 하고, 중간 노드를 m이라고 한다면, 아래와 같은 식을 모든 노드 조합에 반복하는 것입니다.

 

d[s][e] = min(d[s][e], d[s][m] + d[m][e])

 

수도 코드로 표현하면 다음과 같습니다.

d = 인접행렬로 그래프 표현 

for (중간 노드 m in Nodes)

    for (출발 노드 s in Nodes)

        for (도착 노드 e in Nodes)

            d[s][e] = min(d[s][e], d[s][m] + d[m][e])