Shortest Path Algorithm - Dijkstra

Dijkstra

다익스트라 알고리즘은 그래프에서 한 정점에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘이다.

여기서 최단경로란, 정점과 정점 사이를 잇는 간선이 가중치를 가지고 있을 때, 한 정점에서 다른 정점으로 간선을 타고 이동할 수 있는 경로중 가중치의 합이 가장 작은 경로를 말한다. 다익스트라는 한 정점으로부터 다른 정점으로의 최단경로와 그 과정에서 거치는 간선들의 가중치 합을 알아낼 수 있다.

일단, 다익스트라를 설명하기에 앞서 다익스트라는 그래프 내에 음의 가중치 합을 가지는 사이클이 없을 때에만 동작하고, 음의 가중치를 갖는 간선이 없을 경우에만 언급하는 시간복잡도에 동작함을 언급하고 가겠다.

다익스트라는 아래와 같이 동작한다. (가중치를 거리로 표현하겠다.)

처음, 시작점을 제외한 모든 정점과 시작점 사이의 거리를 무한으로 표현한다. 이후 다음 수행을 반복한다.

1. 현재 선택한 정점(처음엔 시작점)에 곧장 연결되고, 아직 방문하지 않은 정점들을 모두 본다.

2. 선택한 정점과 보고있는 정점 사이의 거리와 시작 정점과 선택한 정점까지의 최단거리의 합이 현재까지 구한 시작 정점과 보고 있는 정점 사이의 거리보다 짧을 경우, 이를 갱신해준다.

3. 1, 2번 수행이 모두 끝난 이후, 아직 방문하지 않은 정점들 중 시작점과의 거리가 가장 짧은 정점을 선택한다.

4. 방문하지 않은 정점이 존재하여 정점을 선택했다면, 현재 구한 시작점으로부터의 현재 선택한 정점 사이의 거리는 최단거리이다.

5. 방문하지 않은 정점이 존재하지 않는다면, 수행을 종료한다. 그렇지 않으면 1번으로 돌아가 수행을 반복한다.

위와 같은 동작을 거치는 것으로 시작점에서 모든 정점으로의 최단거리가 구해짐이 보장된다.

증명은 다음과 같다.

1. 시작점은 시작점으로부터의 최단거리임이 보장된다. (거리 0)

2. 시작점으로부터 어떠한 정점으로의 최단경로가 존재한다면, 그 경로의 끝 정점의 이전단계에 있는 정점과 시작점 사이의 경로도 최단경로이다. 만약, 그 경로가 최단경로가 아니라면, 끝 정점과 이전단계 정점을 잇는 간선의 거리와 이전단계 정점의 최단경로를 합한 경로가 현재 경로의 거리보다 더 짧음으로 시작점으로부터 끝 정점까지의 경로가 최단경로라는 가정에 모순이 생긴다.

3. 2번의 귀류증명에 의거하여, 현재까지 알아낸 최단경로를 찾은 정점들부터 바로 이어진 다른 정점으로의 간선을 이은 경로들 중에는 반드시 최단경로임이 보장되는 정점이 하나이상 있다.

4. 3번에 의해 현재까지 최단경로를 찾은 정점들로부터 바로 이어진 다른 정점으로의 간선을 이은 경로들을 찾은 후, 아직 최단경로를 찾지 못한 정점들 중에서 시작점과의 거리가 가장 작은 정점을 최단경로이다.

이는 다른 방법으로도 보일 수 있는데, 최단경로를 찾은 정점으로부터 경로를 만든 이후, 남은 정점들 중에 거리가 가장 작은 정점이 최단경로가 아니라면, 현재까지 최단경로를 찾은 정점으로부터는 새로운 경로를 만들 수 없으므로 남은 정점들 중 거리가 가장 작은 정점 외의 정점들 중 거리가 가장 작은 정점으로의 최단경로가 존재해야 한다. 하지만, 다른 정점에서부터는 어떠한 간선을 통해 거리가 가장 작은 정점을 이어도 현재까지 구한 거리보다 더 커지거나 같아지는 수 밖에 없으므로(다른 정점 자체의 거리가 더 크거나 같고, 간선의 거리가 음이 아니므로), 거리가 가장 작은 정점으로의 경로는 최단경로임이 보장된다.

그래프를 구현하는 방법은 인접행렬과 인접리스트 두 가지 방법이 있는데, 다익스트라를 구현할 때에는 인접리스트가 언제나 더 효율적이므로 인접리스트를 사용하는 것이 좋다.

다익스트라를 구현하는 방법은 크게 두 가지가 있다.

처음 소개할 방법은 다음과 같이 동작한다.

1. 처음, 시작점을 제외한 모든 정점으로의 경로를 무한으로 한다.

2. 선택한 정점(처음엔 시작점)으로부터 바로 이어진 정점으로의 경로를 구하고, 그 경로의 거리가 이어진 정점으로의 거리보다 작을 경우, 경로를 갱신해준다.

3. 모든 정점을 살펴보면서, 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 찾아서 선택해준다. 이후, 모든 정점을 선택할 때까지 2번부터 반복한다.

그래프의 정점 수를 V, 그래프의 간선 수를 E라고 하면, 위 과정에서 정점을 선택하는데에 O(V)이 들고, 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 찾는데에 O(V)이 들어 최대 O(V^2)의 시간복잡도를 갖음을 알 수 있다. (선택한 정점으로부터 바로 이어진 정점으로의 경로를 구하는 단계는 모든 알고리즘이 끝나면 O(E)이다. 양 말단의 정점이 같은 간선의 경우 거리가 가장 낮은 것만 가지고 있으면 되기 때문에 이를 이용하면 언제나 E <= N^2임을 알 수 있다.)

다음으로 소개할 방법은 정점의 수가 많고, 간선 수는 정점의 수에 비해서는 그렇게 크지 않을 때에 사용할 수 있는 방법이다.

min heap을 사용하는 방법인데, min heap이 가지고 있는 정보는 (현재 정점, 시작점과 현재 정점 사이의 거리) 두 가지이며, 시작점과 현재 정점 사이의 거리를 기준으로 min heap을 유지한다.

1. 처음, 시작점을 제외한 모든 정점으로의 경로를 무한으로 한다.

2. 선택한 정점(처음엔 시작점)으로부터 바로 이어진 정점으로의 경로를 구하고, 그 경로의 거리가 이어진 정점으로의 거리보다 작을 경우, 경로를 갱신해주면서 min heap에 추가한다.

3. min heap의 top의 정점을 v라고 할 때에, v가 아직 선택하지 않은 정점일 때까지 heap에서 pop한다. v가 아직 방문하지 않은 정점이라면 그 정점에서부터 2번을 반복한다. 이 반복은 heap이 비어있지 않을 때까지 반복된다.

위의 경우, 최대로 heap에 들어갈 수 있는 원소의 수는 E개이며(거리의 갱신이 일어날 때에, heap에 같은 원소가 여러번 들어갈 수도 있어서 V가 아닌 E이다.) heap의 시간복잡도는 heap에 들어간 원소의 수에 비례하기 때문에 최종 시간복잡도는 O(ElgE)이다. (이 과정에서도 경로를 갱신하는데 들어가는 시간복잡도는 O(E)이다.)

heap을 이용한 방법을 잘 개선, 처리하면 O(VlgV)로 줄일 수 있다고 한다.

음수 간선이 안되는 이유

먼저, 그래프 내에 음수 사이클이 있을 경우, 다익스트라가 동작되면서 무한히 음수 사이클을 돌면서 거리가 작아질 수 있다. 다익스트라에서는 같은 간선을 재이용하는 것을 고려하지 않기 때문에 이 상황에서 최단경로를 구할 수 없다.

다음은 음수 간선을 이용할 경우, 다익스트라의 시간복잡도는 유지되지 않는다.

이는 다익스트라의 '최단경로가 보장되지 않은 남아있는 정점들 중, 최소거리를 갖는 정점은 최단경로이다'가 보장되지 않으면서 발생한다. 최단경로임이 보장되지 않는 정점에서, 음수 간선을 타고 다른 정점으로 이동한 경로가 현재 남아있는 정점들 중 최소거리보다 더 작아질 수 있기 때문이다. 이러한 다익스트라의 성질을 이용하는 문제가 하나 있다. 풀어보면 더 잘 이해할 수 있을 것이다.

APIO 2013 데이터 만들기