[알고리즘 정리] 플로이드-워셜

플로이드-워셜은 음의 가중치가 없는 그래프의 모든 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다.

플로이드-워셜은 다익스트라와는 다르게 음의 가중치를 갖는 간선을 사용할 수 있습니다.

플로이드-워셜도 다익스트라와 같은 memoization 기법을 활용해 거리를 단축시켜 나아가는 방법을 사용합니다.

밑의 그림을 보며 플로이트-워셜 알고리즘에 대하여 알아보겠습니다.

위와 같은 그래프를 통해 인접 행렬을 다음과 같이 나타낼 수 있습니다.

출발 정점에서 목적지 정점으로 가지 못하는 경우라면, 갈 수 없다는 의미의 infinity 값을 설정해 줍니다.

이제 모든 정점을 한 번씩 경유 정점으로 설정하여, 아래와 같은 과정을 반복합니다.

시작 정점 S, 경유 정점 V, 도착 정점 D

S에서 D로의 최단 거리가 S에서 V를 경유하여 D로 가는 거리보다 크면, 그 값을 갱신시켜 줍니다.

if(dist[S][D] > dist[S][V] + dist[V][D])
  dist[S][D] = dist[S][V] + dist[V][D];

1. 1번 정점을 경유해 가는 경우

1번 정점을 제외한 모든 정점들이 1번 정점을 거쳐가는 경우, 1번 정점이 시작 정점 및 도착 정점으로는 사용될 수 없다는 점을 유의해야 합니다. 따라서, 변경이 가능한 부분은 아래 그림의 형광색으로 칠한 부분들이 됩니다.

정점 2와 3은 정점 1을 들렀다 가게 되면 그 비용이 오히려 커지기 때문에 값을 갱신시키지 않습니다.

정점 4는 정점 1을 곧장 들를 수 없기 때문에 값을 갱신시키지 못합니다.

따라서, 1번 정점을 들렀다 가는 경우엔 값의 갱신이 일어나지 않습니다.

2. 2번 정점을 경유해 가는 경우

마찬가지로 정점 2를 경유 정점으로 설정하게 되면, 시작 정점 및 도착 정점으로 사용되지 못합니다.

위의 빨간 글씨로 적힌 숫자들은 더 적은 비용으로 갱신된 거리 값을 나타냅니다.

(1, 4) 위치의 변경된 값을 살펴보면, 기존에는 갈 수 없는 경로로 인식되었지만, 정점 1에서 정점 2를 경유해 정점 4로 가게 되면, 10 + 3의 비용이 발생하는 것을 알 수 있습니다.

나머지 정점 3과 4를 경유해 가는 과정도 거치면 아래와 같은 최소 비용을 갖는 2차원 배열이 완성됩니다.

모든 정점들을 경유 정점으로 설정해 비용을 계산해 최소가 될 가능성을 확인하므로, O(v^3) 의 시간 복잡도를 가집니다.