플로이드의 최단 거리 알고리즘 정리 - (하)

(앞의 (상) 에 해당하는 글을 보지 못하신 분은, 먼저 보고 오시면 좋겠습니다.)

(다시 한 번 적습니다만, 이 책은 [알고리즘 문제 해결 전략] 의 책 내용을 정리한 것입니다,) 

---

 

저번 글에서는, u에서 v까지 가는 경로 중에, S의 원소를 경유점으로 사용하는 최단 경로의 길이는

[1번 식]   로 나타나짐을 살펴보았다.

 

 

이제 이 식을 점화식 형태로 나타내기 위해서, 형태를 살짝 바꾸어 보자.

그래프의 노드의 개수가 V개라면, 각각의 노드들을 0부터 V-1 까지 번호를 붙일 수 있다.

 인 원소 k에 대해서,   이라 하자.

다른 말로 하면, 는 0부터 k까지의 정수를 원소로 갖는 집합이다.

 

이렇게 표현하는 경우, 는 0부터 k까지의 노드의 집합이 되며,

우리가 구하고자 하는 u에서 v까지의 최단 거리는,
'모든 정점을 경유점으로 사용할 수 있을 때'의 최단 거리이므로, 이라고 할 수 있다.

이제 [1번 식]의 S라는 집합을 로 사용하고, 원소 x를 k로 선택해 보자.

이제 위의 식은 다음과 같은 모양이 된다.

 

 

자. 위의 식에서 는 뭐라고 포현할 수 있을까? 그 답은 아래와 같다,

(0부터 k까지의 정수를 원소로 갖는 집합에서, k를 빼는 결과이므로, 이는 이 되는 것이다,)

이 사실을 이용해서, 위에 주어진 식을 다시 한 번 써 보자.

 

 

자. 이제 이 식은 점화식이 되었다.
모든 노드 쌍 u, v에 대해서, 도 를 이용하여 표현할 수 있을 것이고,

그렇게 계속 내려가다 보면, 결국은 모든 값을, 를 이용해서 표현할 수 있을 것이다.

다시 말하면, 모든 값은 의 계산 결과로부터 출발한다고 볼 수 있다.

 

그렇다면, 임의의 노드 쌍 (u, v)에 대해서, 는 어떻게 계산하는가?

이는 어떤 원소도 경유점으로 갖지 않는 (다시 말해, 경유점으로 쓸 수 있는 원소가 하나도 없는) 경우에서의

u에서 v까지의 최단 거리이다.

 

만일 이러한 최단 경로가 있다면, 그것은 바로 u에서 v까지를 직접 잇는 간선이 될 것이고,

이러한 최단 경로가 없다면, 이는 양의 무한대의 값을 갖게 될 것이다.

만일 u와 v가 같은 점인 경우, 이 값은 0으로 한다.

 

이렇게 하여 모든 (u, v) 쌍에 대해  값을 계산했다면,

앞으로는 순서대로 를 계산할 수 있게 되는 것이고,

결국은 임의의 두 점 (u, v)사이의 최단 경로 길이인, 를 구할 수 있게 된다.

 

 

즉, 플로이드 알고리즘에서, 모든 노드 쌍의 최단 거리를 계산하는 방법은 다음과 같다.

1. 모든 노드 쌍 (u, v)에 대해 를 계산한다.

2. 앞의 계산 결과를 바탕으로 를 계산한다.

3. 앞의 계산 결과를 바탕으로 를 계산한다.

....

END. 앞의 계산 결과를 바탕으로 를 계산한다.

이 계산 결과가, 모든 노드 쌍 (u, v) 사이의 최단 경로 길이가 된다.