2024-05-17-19. Dijkstra Algorithm

Shortest Path 문제

Shortest Path 문제는 그래프의 각 노드에 대해, 시작 원소(source node) s로부터의 최단 경로 길이를 찾는 문제이다.

이 문제를 푸는 데 우선순위 큐가 사용된다.

Dijkstra Algorithm

Dijkstra Algorithm은 Shortest Path 문제를 푸는 대표적인 알고리즘이다.

Dijkstra 알고리즘은 그래프의 노드를 다음과 같이 Red 노드와 Blue 노드로 구분한다.

Red Node (빨간 노드)

s로부터의 최단 거리가 구해진 노드는 Red Node가 된다.

Blue Node (파란 노드)

최단 거리가 아직 구해지지 않은 노드는 Blue Node 이다.
Blue Node는 최단 거리 추정값을 갖는다.
여기서 최단 거리 추정값은, s에서 해당 Blue Node에 도달하기 전까지 빨간 노드만 거쳐 갈 수 있다고 가정했을 때의 최단 경로 길이이다.
빨간 노드만 거쳐서 해당 노드까지 도달하는 게 불가능하다면, 최단 거리 추정값이 ∞가 된다.

Dijkstra 알고리즘의 진행

알고리즘 시작 시 노드 세팅은 다음과 같다.

s에서 s까지의 최단 경로는 0임이 자명하므로, s는 빨간 노드이다.
나머지는 일단 파란 노드로 둔다.
s와 간선 하나로 직접 연결되어 있는 노드는, 최단 거리 추정값이 간선의 가중치와 같다.
나머지 파란 노드는 빨간 노드만 거쳐서 도달하는 경로가 없으므로, 최단 거리 추정값이 ∞이다.

여기서 Blue 노드를 Red노드로 하나씩 바꿔 나갈 것이다. 이때 다음 사실을 이용한다.

Blue Node중 가장 최단 거리 추정값이 작은 것은, 추정값이 실제 최단 경로이다.

따라서 추정값이 가장 작은 Blue Node를 바로 Red Node로 바꿀 수 있다.

그 다음, 빨간 노드가 추가되었으므로 나머지 Blue 노드의 최단 경로 추정값을 업데이트해야 한다. 이때 다음 사실을 이용한다.

노드 u가 파랑에서 빨강으로 바뀔 때, u와 간선 하나로 직접 연결된 파란 노드의 추정값만 바뀐다. 나머지 파란 노드의 추정값은 바뀌지 않는다.

따라서 u와 직접 연결된 파란 노드들의 추정값만 업데이트 해 주면 된다.

그 다음 다시 추정값이 가장 작은 파란 노드를 빨강으로 바꾸고, 인접 파란 노드의 추정값을 업데이트하는 과정을 모든 노드가 빨강이 될 때까지 반복하면 된다.

Dijkstra 알고리즘 증명

(노드 u, v에 대해, u에서 간선 하나를 거쳐 v로 가는 경로는 u->v, 간선 0개(u=v인 경우)에서 n개를 거쳐 v로 가는 경로는 u~>v 로 표기함)

먼저 다음 보조 정리를 증명해야 한다.

노드 s, m1, m2 d에 대해, 노드 s에서 d까지의 최단 경로가 s~>m1~>m2~>d라고 가정하자. 위 경로에서 m1~>m2를 p라 하자.
그러면 노드 m1에서 m2까지의 최단 경로는 p이다.
즉, 어떤 경로가 최단 경로이면 그 안의 부분 경로도 최단 경로이다.

증명은 다음과 같다.

만약 p가 m1에서 m2까지의 최단 경로가 아니라고 하자.
그러면 p보다 짧은 m1에서 m2까지의 경로 p’이 존재해야 한다.
p’이 p보다 짧으므로, 경로 s~>p’~>d 는 s~>p~>d 보다 짧다. 그런데 이는 s~>p~>d가 s에서 d까지의 최단 경로라는 위의 가정에 모순된다.
따라서 p는 m1에서 m2까지의 최단 경로여야 한다.

다음으로, 파란 노드 중 추정값이 가장 작은 것은, 추정값이 실제 최단 거리임을 증명해 보자.

가장 추정값이 작은 파란 노드가 b이고, 빨간 노드만 거쳐 b에 도달하는 최단 경로를 p라 하자.
여기서 p가 b로의 최단 경로가 아니라고 가정하자. 즉, p보다 짧은 b로의 경로 p’이 존재한다고 가정하자.

p는 빨간 노드만 거쳐 갔을 때의 최단 거리이므로, 경로 p’은 s에서 b에 도달하기 전 다른 파란 노드를 먼저 거쳐야 한다.
p’에서 최초로 거치는 파란 노드를 v라고 하자. 또한 p’의 s부터 v까지의 부분 경로를 k라 하자.
여기서 k는 빨간 노드만 거쳐서 v로 도달하는 최단 경로이다. 왜냐하면

p’에서 최초로 거치는 파란 노드를 v라고 했으므로, v이전까지는 빨간 노드이다.
위에서 최단 경로의 부분 경로도 최단 경로가 됨을 증명했다. 따라서 k는 v까지의 최단 경로이다.

그런데 b는 가장 추정값이 작은 파란 노드였으므로, 빨간 노드만 거쳤을 때의 최단 경로 p의 길이는 k의 길이 이하여야 한다.
p’의 부분 경로인 k의 길이가 p 이상이 되었으므로, p’의 길이가 p보다 짧다는 것에 모순이 발생한다.
따라서 p는 b로의 최단 경로이고, 추정값이 가장 작은 파란 노드는 추정값이 실제 최단 거리다.

이제 다음 사실을 증명해 보자

노드 u가 파랑에서 빨강으로 바뀔 때, u와 간선 하나로 직접 연결된 파란 노드의 추정값만 바뀐다. 나머지 파란 노드의 추정값은 바뀌지 않는다.

증명 :

노드 u가 빨강으로 바뀌면서 노드 v의 최단 거리 추정값이 바뀌었다고 하자.
이때, v까지 빨간 노드만 거쳐 도달하는 최단 경로에는 u가 있어야 한다. 그렇지 않으면 u가 빨간색이 되기 전에도 해당 경로가 존재했을 것이고, v의 추정값은 바뀌지 않았을 것이다.

s~>u~>x~>v
v까지 빨간 노드만 거치는 최단 경로는 위와 같고, u ≠ x ≠ v 라고 가정하자. 그리고 위에서 s~>u~>x 를 경로 p라 하자.
위의 보조 정리에 따라, p는 x로의 최단 경로이다.
x는 u보다 먼저 빨간색이 되었으므로, u를 거치지 않는 x까지의 또다른 최단 경로가 존재한다. 이 경로를 p’라 하자.
p와 p’ 둘다 최단 경로이므로 길이가 같다. 따라서 경로 p~>v를 p’~>v로 바꿔도 빨간 노드만 거치는 최단 경로이다.

그런데 경로 p’내에는 u가 없다. 따라서 p’~>v 라는 경로 길이는 u가 빨간색이 되기 전에 반영되었어야 하고, 이는 v의 추정값이 바뀌었다는 것에 모순이다.
따라서 u = x여야 한다.
즉, 노드 u가 빨간색이 되고 v의 추정값이 바뀌었다면, 추정 최단 경로에서 u 바로 다음 v가 나와야 한다.

그러므로 최단 경로 추정값은 u의 인접 노드에 대해서만 업데이트 해 주면 된다.
업데이트 값은, (u까지의 최단 거리 + 인접 노드로의 간선 가중치)이다.
단, 인접 노드에서만 추정값이 바뀔 수 있을 뿐, 인접 노드라고 무조건 추정값이 바뀌는 건 아니므로, 원래 추정값이 업데이트 값보다 작다면, 업데이트하지 않는다.

Dijkstra 알고리즘에서 Priority Queue의 사용

Dijkstra 알고리즘에서 파란 노드 중 최단 거리 추정값이 가장 작은 것을 찾는 데 Priority Queue가 사용된다.

Heap으로 구현된 Priority Queue를 사용하면 O(logn) 시간에 추정값이 가장 작은 파란 노드를 찾을 수 있다. 파란 노드의 추정값이 업데이트되면, 해당 노드의 위치만 위로 올리면 된다.

그런데 위의 방법은 추정값이 업데이트된 노드를 heap에서 찾아야 하고, 이것을 구현하는 것이 복잡하다.

따라서 heap에 노드 자체가 아닌, 노드 구분 번호와 해당 노드의 최단 거리 추정값만 복제해서 저장하는 방법이 더 자주 사용된다. 노드의 추정값이 바뀌면 힙 원소의 위치를 바꾸는 대신, 원래 있던 원소들은 놔둔 채로 새로 갱신된 정보를 힙에 insert하면 된다.

새로 갱신된 정보가 오래된 정보보다 우선순위가 높으므로(추정값이 작으므로) 힙에서 먼저 delete 된다. 따라서 갱신되기 전의 데이터가 delete되면, 데이터가 가리키는 노드는 이미 빨간색 노드가 되었을 것이고, 이때는 데이터를 무시하면 된다.

Dijkstra 수행 시간

노드 개수가 n, 간선 개수가 m인 그래프의 Dijkstra 수행 시간을 구해 보자.

알고리즘 시작 시, 먼저 모든 노드를 우선순위 큐에 넣어야 한다.

여기서 n * logn 시간이 걸린다.

다음으로 노드의 추정값이 업데이트될 때마다, 노드의 Heap에서의 위치를 옮겨야 한다. 추정값을 업데이트하는 연산은 간선 하나에 대해 한 번 일어나므로, 이 작업은 mlogn 시간이 걸리다.

힙에서 추정값이 가장 작은 노드를 n번 꺼내는데, 이때 nlogn 시간이 걸린다.

따라서 총 O((n+m)logn) 시간이 걸린다.

만약 heap 내의 노드를 업데이트하는 대신, heap에 노드의 정보를 복제해서 넣는 방식을 사용한다면, heap에 n+m개의 원소가 들어갈 수 있게 된다.

따라서 힙에 업데이트된 정보를 넣는 데 mlog(n+m), 추정값이 가장 작은 노드 정보를 꺼내는 데 (n+m)log(n+m)시간이 걸린다.

n-1 <= m <= n², logn <= log(n+m) <= log(n+n²) <= log(n³) = 3logn

이므로, log(n+m)은 점근적으로 logn과 같다.

따라서 이 방법도 O((n+m)logn) 시간이 걸린다.

← Previous Post Next Post →

목록으로