Show 수학과의 좌충우돌 프로그래밍알고리즘/이론 [Algorithm] 플로이드 와샬(Floyd-Warshall) 알고리즘ssung.k 2019. 11. 10. 21:34 그래프에서 정점끼리의 최단 경로를 구하는 방법은 여러가지가 있습니다. 플로이드 와샬 알고리즘에 대해서 알아보기 전에 이에 대해서 간단히 살펴보도록 하겠습니다.
Floyd-Warshall 알고리즘이란?
알고리즘
다음 그래프에 대해서는 인접행렬 W가 아래와 같이 생기게 됩니다.
이 때 INF 는 무한대로 이동하는 경로가 없다는 의미입니다. 이를 통해 최단경로 행렬 D 를 만들 수 있습니다.
해당 행렬 그렇다면 W 인접행렬을 통해 D 최단경로 행렬을 어떻게 만들 수 있을까요?
다음과 같이 언어로 보는 것보단 수식으로 보는게 더 이해하기 쉽습니다. 이 때 즉 k 라는 정점을 새로 추가하였을 때 i 정점부터 j 정점까지의 최단경로는 기존의 i 정점 부터 j 정점까지 이동했던 경로 와 i 정점부터 k 정점까지의 최단 경로 + k 정점부터 j 정점까징의 최단 경로 중 최소값이 됩니다. 다음과 같은 방법으로 플로이드 와샬 알고리즘은 중간 정점을 모두 실험해보게 됩니다. 전체적인 수도코드는 다음과 같습니다. D 행렬의 변화를 전부 다 확인하기는 힘들 것 같고 W 에 해당하는 D(0) 가 D(1) 으로 바뀌는 과정만 같이 보도록 하겠습니다.
바뀐 부분을 살펴보면 Floyd-Warshall 경로구하기최단 경로 행렬 D 를 통해 i 번째 정점에서 j 번째 정점까지 최단경로를 구할 수 있었습니다. 정확히는 최단경로로 갈 때의 가중치를 구하는 것이기 때문에 어떤 정점을 거쳐 가는지는 알 수 없습니다. 따라서 이를 위해 직전 정점 행렬
예를 들어 1에서 3까지의 경로를 구해보도록 하겠습니다. 예시를 위해 완성된 pi 행렬을 살펴보면 아래와 같습니다.
우선 1 정점에서 출발해서 3 정점에서 끝나므로 경로의 시작은 1, 끝은 3 입니다. 3 직전에 오는 정점은 현재 경로는 1 -> 4 -> 3 이 됩니다. 이제 다시 1 정점에서 4 정점 까지의 경로를 구하기 위해 현재 경로는 1-> 5 -> 4 -> 3 이 됩니다. 1 정점에서 5정점까지의 경로를 구하기 위해 경로가 1-> 1 로 같은 정점이 연속적으로 나온다는 의미는 경로가 완성되었음을 의미합니다. 따라서 완성된 경로는 1-> 5 -> 4 -> 3 가 됩니다. 직전 정점 행렬 pi 행렬도 D 행렬과 마찬가지로 가장 바깥 for 문이 돌면서 갱신이 됩니다. 먼저 pi(0) 부터 본다면 다음과 같습니다.
다음으로 pi(1) 은 다음과 같습니다.
1번 정점을 통해 i 에서 j 까지 경로가 생겼다면 마찬가지로 pi(k) 에 대해서 k 번 정점을 통해서 i 에서 j 까지 경로가 생겼고 그 경로가 최단경로라면 이 과정을 반복한다면 다음과 같습니다.
구현위에서 정의했던 행렬 D 를 graph 행렬로 정의하고, 행렬 pi 를 before 행렬로 정의하였습니다.
|