정점간의 최단 거리를 구하는 알고리즘들에 대해서 한 번 알아보자.

다익스트라

• 단일 시작점 최단 경로 알고리즘

다익스트라 알고리즘은 너비 우선 탐색과 유사 한 형태를 가진 알고리즘으로, 시작점에서 가까운 순서대로 정점을 방문한다. 다만 가중치(거리)가 있다보니 BFS 와 완전히 동일한 방식을 사용할 수는 없다.

우선순위 큐

다익스트라 알고리즘에서는 우선순위 큐 를 활용한다. 우선순위 큐에 대한 자바스크립트의 구현은 여기 를 참고하면 좋을 것 같다.

(정점의 번호, 정점까지의 거리) 를 우선순위 큐에 넣어서 정점까지의 거리를 기준으로 우선순위 큐를 사용한다.

그리고 시작점에서 다른 정점까지의 거리를 저장하는 배열 에 저장하면 된다. (간단히 dist 라고 부르자)

우선순위 큐에서 최단 경로의 정점을 하나씩 꺼내면서 해당 정점과 연결된 정점들을 우선순위 큐에 넣는 것을 반복한다.

만약 v 에 아직 방문하지 않았고, 간선 (u, v) 를 검사한다고 하면 u 까지의 최단 거리에 간선 (u, v) 의 가중치를 더해서 v 까지의 거리를 구한다.

만약 이 거리가 최단 거리라면 dist[v] 를 갱신하고, (dist[v], v) 를 우선순위 큐에 다시 넣는다.

여기서 주의해야할 것은 최단거리는 언제든지 갱신될 수 있다는 점이다.

간선 (u, v) 를 탐색하면서 (dist[v], v) 를 우선순위 큐에 넣었는데 다른 정점을 돌면서 더 짧은 (dist[v], v) 를 우선순위 큐에 넣을 수도 있다.

이렇게 되면 우선순위 큐에 (dist[v], v) 가 여러 개 생길 것이다.

text
Graph:
   A ---- 10 --- B
   |             |
   20            2
   |             |
   D ---- 5 ---- E -- 8 -- C

위의 그래프에서 시작점이 A 라고 하자. 시작점을 탐색하면서 (20, D) 가 우선순위 큐에 들어가게 될 것이다.

그러나 A, B, E 를 탐색하면서 (10 + 2 + 5, D) 도 우선 순위 큐에 들어가게 된다.

이 경우에 (20, D) 는 우선순위 큐에서 pop 된다고 해도 무시되어야 한다.

(20, D) 가 pop 되었다는 것은 이미 이전에 (17, D) 가 pop 되었다는 것이고 dist[D] 는 17 일 것이다.

따라서 dist[D] 와의 비교를 통해서 더 짧은 경로가 이전에 이미 탐색되었는지를 확인하면 된다.

증명

다익스트라의 증명은 귀류법(어떤 명제가 참이라고 가정한 후, 모순을 이끌어내 그 가정이 거짓임을, 즉 처음의 명제가 거짓임을 증명하는 방법) 을 통해 가능하다.

여기서는 다익스트라를 통해 최단거리를 구할 수 없다고 가정하고 모순을 이끌어내려고 한다.

text
Graph:
   A ---- ? ---- B
   |             |
   ?             ?
   |             |
   D ---- ? ---- E -- ? -- C

다시 위의 그래프를 활용해서 이야기해보자.

시작점 A 부터 E 까지의 거리를 구하는 것이 목표이고, 실제로는 A - D - E 가 가장 짧다고 하자.

여기서 다익스트라 알고리즘이 최단 거리를 제대로 구하지 못한다고 가정하기 위해, 다익스트라 알고리즘이 A - B - E 가 가장 짧은 최단경로라는 결론을 내렸다고 가정해보자.

도착점 E 에 도착한 순간, 어떤 정점은 이미 방문을 했을거고 또 어떤 정점은 우선순위 큐에 들어가 있는 상태일 수 있다.

만약 D 를 방문하지 않은 상태라고 가정해보면, D 까지의 최단 거리는 dist[A] + w(A, D) 가 된다. 그런데 이미 방문한 정점 A 를 탐색하면서 D는 무조건 우선순위 큐에 (D, dist[A] + w(A, D)) 로 들어가게 되었을 것이다.

A - B - E 로 진행하면서 E 또한 우선순위 큐에 들어가게 될텐데 여기서 이미 들어가있던 D 가 아닌 E 가 pop 되었다는것은 dist[E] 가 dist[D] 보다 작았기 때문이다.

즉 dist[D] ≥ dist[E] 라는 소린데, 이는 D 를 거쳐서 A 에서 E 로 가는 것이 가장 짧은 경로라면 성립할 수가 없다.

음수 가중치를 계산할 수 있는가?

일반적으로 다익스트라 알고리즘은 음수 가중치가 있다면 정확한 최단 거리를 계산하지 못한다.

음수 가중치가 있다는것은 이미 최단거리로 처리된 노드가 나중에 더 최단거리로 갱신될 가능성이 있다는 것이기 때문이다.

text
Graph:
   A ---- 10 --- B
   |             |
   20            2
   |             |
   D ---- 5 ---- E -- -100 -- C

다익스트라를 돌면서 E 의 최단 거리는 (10 + 2) 가 되겠지만 실제로는 10 + 2 - 100 이다.

다시 말해서 이미 처리된 정점이 최단 거리라는 가정을 깨뜨릴 수 있다.

만약 이미 처리된 정점이 최단 거리라는 가정을 버리고 (방문한 정점에 대한 기록을 하지 않고) 다익스트라를 작성한다면 음수 가중치를 계산할 수도 있다. 하지만, 이 경우에는 시간 복잡도가 정점의 갯수에 대해 지수함수로 증가할 수 있기 때문에 굳이 이런 식으로 다익스트라 알고리즘을 쓸 이유가 없다.

시간 복잡도

다익스트라의 시간 복잡도는 각 정점마다 인접한 간선들은 모두 검사 하는 작업과 우선순위 큐에 원소를 넣고 삭제 하는 작업으로 나눌 수 있다.

각 정점마다 인접한 간선들을 모두 검사

정점의 갯수를 E, 간선의 갯수를 V 라고 할 때,

각 정점마다 인접한 간선들을 모두 검사하는 작업은 정확히 모든 간선을 1번씩 검사하기 때문에 O(E) 의 시간이 걸리게 된다.

우선순위 큐에 원소를 넣고 삭제

우선순위 큐에 원소를 넣고 삭제하는 작업에서 최악의 경우에는 그래프의 모든 간선이 검사될 때마다 dist 배열이 갱신되면서 동시에 우선순위 큐에 정점의 번호가 추가되는 것이다.

_다익스트라 최악의 경우 _

위의 그래프에서 왼쪽의 핑크색 1번이 시작점이라고 하자.

1번에서 2, 3, 4 까지의 dist 배열은 각각 6, 10, 15로 갱신되면서 우선순위 큐에 (2, 6), (10, 3), (15, 4) 로 들어갈 것이다.

그러고 나서 2번 정점을 탐색하면서 dist[3] 은 6 + 3 으로 갱신되고, 우선순위 큐에 (9, 3) 이 추가 된다.

이제 3번 정점을 탐색하면서 dist[4] 도 10 + 3 으로 갱신되고, 우선순위 큐에 (13, 4) 로 갱신 된다.

이처럼 최악의 시나리오에서는 각 간선마다 한 번씩 추가가 되고, 우선순위 큐에 원소를 추가하거나 삭제하는데 O(logE)의 시간이 걸리고 이를 O(E) 개의 원소에 대해 작업을 해야하므로 O(ElogE) 가 된다.

일반적인 시간 복잡도

위의 두 과정을 더하게 되면 O(E + ElogE) = O(ElogE) 가 되는데, 보통 그래프에서 간선의 개수 E 는 V^2 보다 작기 때문에 O(logE) = O(logV) 라고 볼 수 있다. 따라서 O(ElogV) 라고 할 수 있다.

경로 추적

다익스트라 알고리즘을 통해 최단 거리뿐만 아니라 최단 경로를 구하려면 정점에 도착하기 직전의 정점을 기록해서 역추적을 하면 된다.

벨만 포드

다익스트라 알고리즘과 똑같은 단일 시작점 최단 경로 알고리즘이지만, 음수 가중치가 있는 그래프에서도 최단 경로를 찾을 수 있다.

또한 음수 사이클이 있어서 최단 거리를 제대로 구하지 못하는 경우도 알 수 있다.

벨만포드 알고리즘은 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤, 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식이다.

알고리즘 동작

시작점 s, 도착점 d , dist[k] = 시작점부터 k 까지의 최단 거리 , w(u, v) = u와 v 사이의 간선 가중치 라고 하자. upper[k] 는 현재까지 계산된시작점부터 k 까지의 최단 거리이다.

• 우선 맨 처음에는 시작점부터 시작점사이의 거리가 0이라는 것을 제외하면, 아무것도 알고 있는 것이 없다. 따라서 upper[s] = 0 으로 초기화하고 나머지는 양의 무한대 혹은 매우 큰 수로 초기화한다.

완화

이제부터 우리는 upper 배열의 값을 점차 실제 최단 거리에 가깝도록 줄여나갈 것이다. 그러려면 최단 거리의 특성을 이용해야 하는데, 아래의 특성을 살펴보자

dist[v] ≤ dist[u] + w(u, v)

dist[v] 는 v 까지 최단 거리인데, 만약 u를 거쳐서 v 로 오는 거리가 더 짧다면, u를 거쳐오는 거리가 최단 거리여야한다. 그렇기때문에 dist[v] 가 최단 거리라는 가정에 위배된다.

이번에는 upper[u] + w(u, v) < upper[v] 인 상황을 생각해보자.

upper[v] 를 upper[u] + w(u, v) 로 줄이려고 하는 것이 이번 과정의 목표이다.

u 까지의 최단 거리는 항상 upper[u] 보다 작거나 같을 것이다.

여기서 upper[u] + w(u, v) 는 u를 거쳐 v 로 가는 경로 이므로 만약 upper[u] + w(u, v) 가 upper[v] 보다 작다는 것은, u를 거쳐서 v 로 가는 것이 현재까지 계산된 v로 가는 최단 거리보다 짧다는 것이다.

즉 upper[v] 를 upper[u] + w(u, v) 로 갱신할 수 있다.

이러한 과정을 완화 라고 하고 이를 계속 수행하면서 최단거리가 되도록 한다.

완화를 얼마나 해야하는가?

image.png

최단거리는 결국, 어느 한 지점까지의 최단거리에서 간선을 더한 값으로 완화되어야 한다.

무슨 이야기냐 하면 시작점 s 에서 연결된 정점 a 가 있다고 하자.

모든 간선을 순회하면서 한 번씩 완화를 시도했다고 하자.

이때 upper[a] 는 upper[s] + w(s, a) 로 완화될 수 있다. 그런데 upper[s] 는 시작점 s 부터 s 까지의 거리이므로 당연히 0이 된다.

즉, upper[a] 는 w(s, a) 로 완화될 수 있다. w(s, a) 로 완화하고 나면, 시작점 s 부터 a 까지의 가는 경로중에 w(s, a) 보다 짧은 거리가 있을 수 있을까?

없다. 위의 그래프에서 s 에서 b 로 가는 최단 거리가 s → b 말고 더 있을 수는 없다.

여기서 만약 s → b → c → b 가 더 짧을 수도 있지 않을까 라는 생각이 들었다면 이는 음수 사이클이다. 이 경우에는 s→ b → c → b 보다 s → b → c → b → c → b 가 더 짧고 이를 무한반복하면 당연히 더 짧아진다.

음수 사이클은 기본적으로 존재하는 순간 모든 그래프에서 최단 경로라는 말을 사용할 수가 없다.

이는 조금 뒤에서 더 자세히 살펴보자.

그래서 전체 간선에 대한 완화를 몇 번이나 수행해야 하는가?

위의 그래프를 보면 전체 간선에 대한 완화를 1회 수행하면, a와 b 까지의 최단 거리를 구할 수 있다.

2번 수행하면 c, 3번 수행하면 d 까지의 거리를 구할 수 있다.

만약 s → a → b → c → d 의 모양을 가진 그래프라면 어떨까?

총 4회에 거쳐 a, b, c, d 까지의 최단 거리가 완화될 것이다.

다시 말해서 정점의 갯수가 V 개 일때, 아무리 많이 해도 V - 1 번이면 모든 정점들까지의 거리가 최단 거리로 완화된다.

음수 사이클

image.png

위의 그래프를 한 번 살펴보자. A → B → C 경로를 살펴보면 A → B 는 1 이 필요한데 B → C → A 는 가중치의 합이 -3 이다. A → B → C → A 는 결국 -2 의 가중치를 갖는다.

어떠한 사이클이 합이 음의 가중치를 가지는 순간, 이 사이클을 무한 반복 함으로써 가중치의 합도 음의 무한대를 가지게 할 수 있다.

다시 말해서, 정점의 개수를 V 라고 할 때, 완화가 V - 1 번 이후에도 계속 이루어진다.

이렇게 보면 음수 사이클을 판별하는 방법은 쉽다.

V - 1 번까지 완화를 진행하고 V 번째 완화를 시도해보면 된다. 만약 완화가 이루어졌다면 음수 사이클이 존재하는 것이다.

경로 추적

벨만 포드의 경로 추적은 다익스트라의 경로 추적과 유사하다. 다익스트라처럼 역추적을 하면 되는데,

각 정점을 마지막으로 완화시킨 간선들을 토대로 역추적하면 된다. (이 간선들은 항상 최단경로의 위에 있기 때문)

경로 존재 유무 판별하기

시작점 s 에서 u 까지의 경로가 있는지 판별하는 방법은 쉽게 생각하면 upper[u] 가 Infinity 가 아니면 경로가 있다라고 착각할 수 있다.

경로가 있으면 무조건 완화가 이루어질 것이라고 생각할 수 있기 때문이다. 하지만 음수 사이클이 있다면 이야기가 조금 달라진다.

image.png

위처럼 시작점 s 가 다른 정점들과 간선이 없다고 해도, a ↔ b 사이의 음수 사이클을 통한 완화가 이루어질 수 있다.

따라서 경로의 존재 유무를 판별하려면 upper[u] 가 Infinity 인지 아닌지로 판별하는 것이 아닌, 적당히 큰 값 M 에 대해서 upper[u] < Infinity - M 인지를 확인해야 한다.

적당히 큰 값 M..?

M 은 그러면 어떻게 결정할 수 있을까?

우리는 위에서 완화를 최대 V - 1 번 진행한다고 했다. 그렇기 때문에 음수 사이클을 돌면서 완화된다고 했을 때, 한 번의 완화에 가장 많이 완화되는 값은 가장 작은 가중치값의 2배를 넘지 않을 것이다.

위의 그래프에서는 한 번의 완화당 -1 씩 (-2 + 1) 작아진다.

따라서 (가장 작은 가중치 * 2) * (V - 1) 로 M 을 설정하면 될 것 같다.

시간 복잡도

벨만 포드 알고리즘은 모든 간선을 순회하는 작업을 정점의 갯수 - 1 번 만큼 진행한다. 음수 사이클을 판별하려면정점의 갯수만큼 진행하면 된다.

따라서 O(E * V) 가 된다.

정점의 갯수 : V, 간선의 갯수 : E

플로이드

다익스트라와 벨만 포드 알고리즘은 모두 한 시작점에서 다른 모든 정점까지의 거리 를 구하는 알고리즘이었다. 플로이드는 한 시작점이 아닌, 모든 정점에서 모든 정점까지의 거리를 구할 수 있는 알고리즘이다.

사실 플로이드를 굳이 안쓰고 모든 정점에서 한 번씩 다익스트라 알고리즘을 수행해도 구할 수 있다. 음수 가중치가 있다면 모든 정점에서 벨만 포드 알고리즘을 쓸 수도 있다.

하지만 이런 방법보다는 더 빠르게 수행할 수 있는 알고리즘이 플로이드 와샬 알고리즘이다.

플로이드 알고리즘은 생각보다 간단하다.

정점 u 에서 v 까지의 거리를 dist[u][v] 라고 정했을 때 3중 for 문을 돌면서 u → ? → v 로 갔을 때, 거리가 갱신되는지 살펴보는 것이다.

그런데 플로이드 알고리즘의 프로토타입을 글로 읽고 이해하려니 꽤나 많은 생각을 거쳐야 했다.

프로토타입

image.png

image.png

• 위의 표현식은 a 에서 출발하여 c, d 를 거쳐 b 로 가는 경로이다.

위의 그래프에서 정점들의 집합을 S 라고 하고, 임의의 점을 x 라고 하자.

a 에서 f 로 가는 경로에서 x 를 경유하는 것과, 경유하지 않은 것을 나누어 나타내면

image.png

기호가 너무 많아서 햇갈릴 수 있는데 a → f 의 경로는 x 를 경유해서 가는 것과 경유해서 가지 않는 것의 최소값이라는 의미일 뿐이다.

여기서 이 점화식을 살짝 수정해서 더 보기 좋게 만들어보자.

image.png

이렇게 두 가지의 식을 활용해서 위의 식을 바꾸면

image.png

이 된다.

이제서야 우리가 자주 보던 점화식같이 생겼다.

여기서

image.png

이렇게 두 식의 차이점에 대해서 한 번 생각해보자.

image.png

위의 식은 k 를 거치지 않고 a 에서 k 까지 가는 경로를 의미한다.

image.png

반대로 위의 식은 k 까지 거쳐서 a 에서 k 까지 가는 경로를 의미한다.

그런데 k 까지 가는데 k 를 거치든 안거치든 그게 다를 수 있나?

도착점이 k 이므로 k를 거치는것과 안거치는것은 당연히 같다.

따라서 위의 식이 같다라고 생각하게 되면 식은 더욱 간단해진다.

image.png

이제 우리가 알던 플로이드 알고리즘인, 경유점 하나를 거쳐서 가는것과 안거쳐서 가는 것 중에서 더 짧은 것을 선택하는 식이 된다.