[알고리즘] ASP(3) - 플로이드 워셜 알고리즘 ( Flyod-Warshall Algorithm)

1. 플로이드 워셜 알고리즘과 최단경로와 행렬곱 알고리즘의 비교

이번에는ASP의 두 번째 알고리즘 플로이드 워셜 알고리즘에 대해 알아보겠습니다.

플로이드 워셜 알고리즘은 이전 글에서 알아본 최단경로와 행렬곱 알고리즘과 유사하지만, 연산이 적습니다.

[ 최단경로와 행렬곱의 재귀적 해법 ]

최단경로와 행렬곱 알고리즘에서는 k가 1부터 n( 정점의 개수 )까지 움직이면서 연산을 합니다.

즉 다음 인접행렬의 한 원소를 구하기 위해서는 n번의 연산을 한 후에 최소 값을 구할 수 있습니다.

플로이드 워셜 알고리즘에서는 k가 움직이지 않고 현재 구하고자 하는 차수가 인접행렬이 k 값이 됩니다.

위의 재귀적 해법의 식에서 m = k 가 되는 것이죠.

플로이드 워셜 알고리즘의 재귀적 해법의 식을 이끌어내는 과정이  행렬곱 알고리즘과 다른데 굳이 위의 내용을 언급한 이유는 재귀적 해법의 식 구조가 유사하기 때문입니다. 미리 결과를 알고 재귀적 해법의 식을 이해하면 좋을 것 같아서 언급을 해보았습니다.

2. 플로이드 워셜 알고리즘의 동적계획법 - 최단경로의 구조

두 정점의 최단 경로가 일 때,

최단경로의 중간 정점은 의 양 끝 정점 을 제외한 입니다.

플로이드 워셜 알고리즘은 어떤 한 정점이 중간 정점 집합의 한 원소가 되는지 안되는지를 확인하는 것입니다.

예를들어 -> 의 최단경로의 중간 정점 집합을 라고 할 때

어떤 새로운 정점 가 중간 정점 집합에 포함되서 더 비용이 적은 최단 경로를 만드느냐, 아니면 기존의 중간 정점 집합을 유지시키는 것이 최단 경로이느냐를 판단하는 것이 플로이드 워셜 알고리즘입니다.

가 추가되어서 새로운 중간 정점 집합 를 만드는 것이 가능한 이유는 가중치가 음수가 될 수 있기 때문입니다.  즉 와 인접한 간선 중 음의 가중치가 있다면 더 비용이 적은 최단 경로를 만들수가 있겠죠.

이러한 최단경로의 구조적 특성을 이용해서 재귀적 해법의 식을 만들어보겠습니다.

3. 플로이드 워셜 알고리즘의 동적계획법 - 재귀적 해법

 : 모든 중간 정점이 집합 에 속하는 정점 i에서 j까지의 최단경로의 가중치 라고 정의하겠습니다.

그러면 는 위에서 말씀드린 최단경로의 구조적 특성을 이용해서 다음과 같은 식으로 표현할 수 있습니다.

를 구한다는 것은 가  의 중간정점 집합에 포함될 것인지 안될 것인지를 구하는 것입니다.

만약 를 에 포함시켜봤자 최단경로의 가중치가 변하지 않는다면 입니다.

즉 를 그대로 유지합니다.

만약 를  에 포함시키면 최단경로의 가중치가 더 낮아진다면  입니다.

이를 그림으로 표현하면 다음과 같습니다.

p1, p2는 의 중간 정점 집합입니다.

원래는 하나의 집합인데 가 중간에 포함되었다는 것을 표현하기 위해 나눴습니다.

4. 플로이드 워셜 알고리즘

그래프의 초기 모습을 인접행렬로 표현했습니다.

인접행렬의 원소는 그래프의 가중치입니다.

와 비교했을 때 업데이트된 원소는 빨간색으로 표시된 원소뿐입니다.

먼저 의 원소 값이 5인데, 5가 나온 과정을 수식으로 표현해보겠습니다.

이런 식으로 i , j ,k 에 적절히 값을 대입하시면 구할 수 있습니다.

가 되었으니 이 경우는 을 의 중간정점 집합에 포함시키는 것이 최단 경로가 된다는 것입니다.

실제로 경로의 가중치는 이고,

경로의 가중치는 입니다.

플로이드 워셜 알고리즘의 결과는 위 그림과 같습니다.

실제로 하나하나씩 해보면 결과를 확인할 수 있습니다.

 : 모든 중간 정점이 집합 에 속하는 정점 i에서 j까지의 최단경로의 " 가중치 "였습니다.

즉 인접행렬 로 부터 알 수 있는 모든 쌍의 최단경로 비용입니다.

그런데 최단경로 그 자체를 구하고 싶을수도 있습니다.

그럴 땐 선행자 인접행렬()을 추가하여 표현할 수 있습니다.

선행자 인접행렬은 다음과 같은 식으로 표현할 수 있습니다.

간단히 말하면 가 업데이트 되면 라는 뜻입니다.

은 선행자 인접행렬의 초기화된 모습이며,

은 위의 식을 적용한 모습입니다.

과 비교했을 때 달라진 원소는 빨간색으로 표시한 부분이며,

이는 에서 업데이트 된 원소의 위치와 정확히 일치합니다.

그리고의 원소에 할당하는 값은 현재의 k값입니다.

선행자 행렬의 결과는 위와 같습니다.

인접행렬을 해석하는 방법은 다음과 같습니다.

예를들어 의 최단 경로를 알고 싶습니다.

가 결과이므로 에 대해서, 

입니다.

이 때 얻은 3에 대해서 의 값을 확인합니다.

이네요.

또 4에 대해서 의 값을 확인합니다.

이네요.

이제 더 이상 진행할 수 없으므로 결과를 종합합니다.

의 최단경로의 중간 정점은 가 됩니다.

즉 이 나오기 이전 값부터 거꾸로 올라가면 됩니다.

이 나오기 이전 값은 무조건 최단 경로의 시작점(여기서는 )이고,

마지막 정점은 무조건 최단 경로의 끝점(여기서는 )가 됩니다.

실제로 가 의 최단경로인지 확인해보세요 !

5. 수도코드

코드는 간단하므로 따로 설명할 필요가 없을 것 같습니다.

처음에 살펴봤던 재귀적 해법의 식이 그대로 표현됐네요.

시간복잡도

시간복잡도도 간단하게 계산됩니다.

for문이 중첩으로 3번 수행되므로 시간 복잡도는 입니다.

이상으로 플로이드 워셜 알고리즘에 대해 알아보았습니다.

플로이드 워셜 알고리즘도 수식이 많아서 복잡해보일 수 있는데 예시를 보시면 금방 이해가 되실거라 생각합니다.

플로이드 워셜 알고리즘은 모든 정점에 대해 모든 정점의 최단 경로를 구할 수 있는 알고리즘입니다.

사용된 개념은 중간정점과 인접행렬이었습니다.