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

플로이드의 모든 쌍 최단 거리 알고리즘

 

(이 내용은 '알고리즘 문제 해결 전략' 의 내용을 정리한 것입니다.)

 

---

1. 플로이드의 최단 쌍 알고리즘의 기본적인 개념

 

그래프 내의 어떤 두 점을 u와 v라고 할 때, u에서 v로 가는 경로가 있다고 하자.

이 두 점을 잇는 경로는, u와 v를 직접적으로 연결하는 하나의 간선일 수도 있고,

아니면 다른 점들을 거쳐서 가는 경로일 수도 있다.

 

후자의 경우, 예를 들면 u - a - b - c - v 와 같은 형태가 될 것이다.

이렇게 u에서 v로 가는 경로가 다른 점을 경유해서 가는 경우, 이 경유하는 점들을 경유점이라 하자.

즉, 위에 예로 든 경로에서는 a, b, c가 경유점이 된다.

 

정점 집합 S에 포함된 정점만을 경유점으로 사용해서, u에서 v로 가는 최단 경로의 길이를

라 하자.

예를 들어, S = {a, b, c, d, e, f} 이고, u - a - b - c - v가 u에서 v로 가는 최단 경로라면,

가 된다. ( w(i, j) 는 i와 j를 잇는 간선의 길이이다.)

 

여기서 주의하고 넘어갈 것은,

 - 위의 예에서 보듯, S의 모든 정점을 경유점으로 사용할 필요는 없다.

 - 만일 u에서 v를 잇는 경로가 없는 경우,

는 양의 무한대로 한다.

 

 

S가 공집합인 경우, 경유점으로 사용할 수 있는 점이 없으므로, 최단 거리는 u와 v를 직접 연결하는 간선의 길이와 같다.

즉,

가 되는 것이다.

 

 

우리가 구하고자 하는 것은, 모든 정점을 경유점으로 사용해도 된다고 할 때의

u와 v 사이의 최단 경로 길이를 구하는 것이다.

다시 말해, 모든 정점의 집합을 V라고 한다면,

가 우리가 원하는 답이 되는 것이다.

 

---

 

이제 '표현법'을 익혔으니, 플로이드 알고리즘의 기본적인 아이디어로 들어가보도록 하자.

S중에 정점을 하나 골라서 이를 x라 하자.

S를 경유점의 집합으로 사용하면서 u에서 v로 가는 최단 경로는, 점 x를 경유할 수도 있고, 그렇지 않을 수도 있다.

두 가지를 각각 살펴보자.

 

Case 1 > 최단 경로에 x가 포함되지 않은 경우. (ex. u - a - b - c - v)

 - 이 경우는, x가 경유점으로 사용되지 않는다는 말과 같다.

 - 즉, 이 경로를 만드는 데에는 x가 필요하지 않으므로,

와 같다.

 

Case 2 > 최단 경로에 x가 포함된 경우. (ex. u - a - x - b-  c - v)

 - 이 때는, 이 최단 경로를 u부터 x까지의 최단 경로와, x에서 v까지의 최단 경로로 나눌 수 있다.

   ( 위의 예를 들면, u - a - x 와 x - b - c - v 두 개의 경로이다.)

   (나누어진 경로 두 개 모두 각각의 최단 경로가 되는 이유는 간단하다. 
    만일 u - a - x보다 짧은 u -> x 경로가 존재하면, 그 경로를 따라서 u에서 v로 가는 것이 훨씬 짧기 때문이다.)

 - 따라서,

이다.

 - 그런데 여기서, x는 두 경로 중 어디에서도 경유점으로 사용되지 않으므로, S대신 S - {x}로 써도 같은 결과이다.

 - 따라서

로 쓸 수 있다.

 

 

두 경우를 합치면, S의 원소를 경유점으로 사용하면서, u에서 v로 가는 최단 경로는

x를 포함하지 않던지, 포함하던지 둘 중 하나이므로, 두 경우 중에 더 짧은 경로가 될 것이다.

 

이를 [1번 식] 이라 하자.

 

 

위 식의 정당성 증명과 이해를 위해서, 예를 들어보자.

u에서 v를 잇는 최단 경로를 u - a - b - c - d - v라 하고, S는 알파벳 a부터 p까지의 집합이라고 하자.

이제, 어떤 x를 선택하느냐에 따라서 두 가지의 값이 어떻게 달라지는지를 살펴보자.

 

[경우 1] 경유점에 사용되지 않는 정점 (예를 들면, f )를 x로 선택했다고 해 보자. 이 경우에 두 가지 값을 따져보면,

 

1) 

 이 식의 값은, 우리가 찾는 최단 경로 u - a - b - c - d - v의 길이와 같다.

    원래 최단 경로는 f를 포함하지 않았기 때문이다.

 

2) 

 이는, u에서 v까지의 모든 경로들 중 [점 f를 경유하는 경로들 중에서 최단 길이] 이므로,

    더이상 최단 경로가 되지 못한다. 이런 경로의 예를 들면, u - j - f - k - v 와 같은 경로가 될 것이다.

    만일 f를 경유하면서 u에서 v로 갈 수 있는 경로가 없다면, 이 값은 양의 무한대가 될 것이다.

    둘 중 어느 경우이든, 2)의 값은 항상 1)의 값보다 크다. 따라서, 식 1은 성립한다.

 

 

[경우 2] 이번에는  경유점에 사용되는 정점 (예를 들면, c )를 x로 선택했다고 해 보자. 이 경우에 두 가지 값을 보면,

 

2) 이번엔 아랫줄을 먼저 살펴보자. 

의 값은, u - a - b - c 와 c - d - v 의 두 경로의 길이를

    합친 것이다. 따라서, 이 식의 값은  원래의 최단 경로인 u - a - b - c - d - v 의 길이와 같다.

 

 

1)

 이 식의 값은, 더 이상 우리가 찾는 최단 경로 u - a - b - c - d - v의 길이가 되지 못한다.

    이 경로에서는 더 이상 c를 경유점으로 사용할 수 없기 때문이다.

    즉, 이 식의 값은 위 경로가 아닌 다른 경로를 통해서 u -> v로 가는 경로의 길이가 되거나,

    또는 그런 경로가 존재하지 않는다면 양의 무한대의 값을 가지게 될 것이다.

    둘 중 어떤 경우이던지, 이는 2)의 값보다 큰 값이 된다.

 

 

[경우 1]과 [경우 2]에서 볼 수 있듯이, 어떤 점을 x로 선택했는지와는 관계없이 [1번 식]이 성립한다.

 

_____________________

 

추후 추가 예정.

앞으로의 전개 내용은 - 저 식이 점화식이라는 것.