[Algorithm] 다익스트라 알고리즘 (Dijkstra algorithm)

 다익스트라 알고리즘은 최단경로를 탐색하는 알고리즘이며, 2차원 배열을 이용하여 구현시 O(N^2)의 시간복잡도를 가지고 힙(Heap)을 이용하여 구현하면 O(ElogN) 시간안에 탐색할 수 있는 알고리즘입니다.

 

다익스트라 알고리즘은 한 지점(S)에서 목적지 지점(E)로 이동할 수 있는 최단 경로를 탐색할 수 있으므로 단일 출발, 단일 도착 최단경로 문제에 활용될 수 있습니다. 단, 음수 가중치를 가지는 그래프에서는 사용할 수 없다는게 단점입니다. 왜 그런지는 잠시 뒤에 알아보겠습니다.

 

 

 

1. 다익스트라 알고리즘 

 

 

 

시작점 S 에서 출발해 연결되어 있는 간선을 모두 방문한 뒤 해당 노드에 있는 값(경로 값, 초기 값은 무한대)보다 작으면 갱신시켜 줍니다.

 

그 다음 연결되어 있는 Edge 중에서 현재 가중치와 더해 가장 작은 값을 가지고 있는 edge를 선택하여 나아갑니다.

 

이 때, 선택한 노드는 더 이상 바뀔 수 없는 최단 거리입니다.

 

그림을 통해 한 번 보겠습니다.

 

 

 

 

 

 

S에서 E 로 가는 최단 경로를 다익스트라 알고리즘을 통해 한 번 찾아 보겠습니다.

 

먼저 출발점 S는 가중치가 0 이므로 0으로 초기화 시키고, 나머지 지점들은 무한대로 초기화 시킨 상태에서 시작합니다.

 

 

 

 

 

S 에서 갈 수 있는 지점들의 가중치를 변경합니다. 초기 무한대 값보다 출발점 S의 가중치 (0) + edge의 가중치 가 작으므로 2번 정점과 3번 정점은 각각 8과 1로 값이 변경됩니다.

 

즉, 2번과 3번 정점으로 갈 수 있는 경로중 현재까지 가장 낮은 가중치가 8과 1이라는 이야기입니다. 이 값은 추후 다익스트라 알고리즘을 수행하며 바뀔 수도 있고 안바뀌고 유지될 수 도 있습니다. 그 다음 과정이 중요합니다.

 

그 다음 방문 할 수 있는 정점중 제일 작은 곳을 찾아 경로를 확정합니다. 경로로 확정된 정점은 추후에 값이 바뀔일이 없습니다. 

 

 

 

이와 같이 3번 정점을 선택하고 경로를 확정합니다. 그런데 선택한 정점은 왜 더 이상 바뀔일이 없을까요? 그 이유는 다익스트라는 음의 가중치를 가질 수 없기 때문입니다. 만약 경로가 확정된 정점의 값이 바뀔일이 생긴다면 그건 모순입니다. 모순에 대해서는 예시가 끝나고 설명드리겠습니다.

 

경로가 확정된 그룹을 Cloud 라고 부르겠습니다. 3번정점을 선택한 후 3번 정점에서 뻗어나갈 수 있는 지점을 탐색하며 해당 지점의 가중치를 갱신시켜줍니다.

 

 

 

 따라서 4번 지점과 5번 지점에 3과 4로 채워집니다.

 

4번 정점은 3번정점까지의 거리(1) + 3번과 4번까지의 거리(2)를 더해서 3이 됩니다.

 

5번 정점은 3번정점까지의 거리(1) + 3번과 5번까지의 거리(3)을 더해서 4가 됩니다.

 

이제 Cloud 에서 뻗어나갈 수 있는 edge는 모두 3개입니다. 1->2, 3->4, 3->5 입니다. 이중 최소 가중치를 가지는 4번정점을 선택하여 경로로 확정짓습니다.

 

 

현재 Cloud 에는 1번,3번,4번 정점이 있게 되고 1->3->4로 가는 경로는 최단 경로라고 말할 수 있습니다.

 

이제 4번정점을 Cloud 에 포함시켰으니 4번정점에서 뻗어나갈 수 있는 지점의 값을 갱신 시켜줍니다.

 

 

이렇게 되는데! 마지막 도착지인 7번 지점의 값이 바뀌었다고 1->3->4->7 경로가 아직까지 최단경로라고 단정 지을 수 없습니다. 다른곳으로 돌아서 7번 지점으로 갈 수 있기 때문이죠. 7번 정점이 경로로 확정되기전까지는 단정지을 수 없습니다.

 

또 Cloud 에서 갈 뻗어나갈 수 있는 것 중 가장 최소를 선택합니다.

 

 

5번정점이 선택되었고 7번 정점의 값이 5번 정점까지의 최단경로 값(4) + 5->7 가는 edge 가중치(1) 값이 더해져 5가 되었습니다. 기존에 7번 정점에 있던 15 보다 작으므로 5로 갱신시켜줍니다.

 

이제 다시 Cloud 에서 뻗어 나갈 수 있는 것중 가장 최소를 선택합니다.

 

 

도착점인 7번 정점이 경로로 확정되었음을 볼 수 있습니다. 따라서 S->E로가는 최단경로는 1->3->5->7 입니다. 가중치는 5이죠.

 

 

여기서 의문이 하나 들 수 있는데 1->2 경로로 가서 7번 정점까지 갔을 때 현재 가지고 있는 5라는 값보다 더 작은 값이 나올 수 있지 않을까? 라는 의문입니다. 위의 예시 설명할 때도 언급했던 모순 얘기와 같이 풀어보겠습니다.

 

 

 

 

마지막까지 다 한 그래프의 모습입니다. 1->2->6->7 경로는 기존값인 5값보다 작은 값이 안나왔습니다. 우연일까요? 아닙니다. 

 

결론적으로 말씀드리면, 경로가 확정된 지점으로 가는 다른 경로가 있을 때, 그 경로가 확정된 지점의 값을 갱신시킬 수 있다면, 즉 확정된 지점이 가지고 있는 가중치보다 더 작다면 애초에 다익스트라는 그 경로를 찾았을 것입니다.

 

 

 

쉽게 예를 들어 설명해보겠습니다.

 

 

 

 

시작점은 1번 정점입니다. 1->3 으로가는 가중치와 3->2로 가중치를 알 수 없다고 할 때, 만약 2번 정점이 Cloud 에 포함되었다면?? 1->3->2로 가는 경로가 최단 경로가 될 수 있을까요?

 

 

 

다익스트라 알고리즘에서 2번 정점을 Cloud 에 포함시켰다는건, 1->2 로 가는 경로가 1->3 으로 가는 경로보다 가중치가 같거나 더 작았기 때문입니다. 따라서 1->3으로 가는 가중치를 x라고 하면 x는 x>=10 입니다. 따라서 x + (3->2) 가는 가중치를 더했을 때 최소 10이상은 나온다는 말입니다. 따라서 1->3->2 경로로 2번 정점의 값을 갱신 시킬 수 없습니다.

 

 

 

 

2. 왜 음수인 가중치를 사용할 수 없을까??

 

 

 

 

2가지 예로 설명드리겠습니다.

 

(1) 무한 루프

 

윗 그림과 같은 그래프가 있다고 칩시다. 1번에서 다익스트라를 돌려 2번까지 가는 최단 경로를 알고 싶은데 음수 가중치가 포함되어 있습니다. 1번에서 2번으로 갈때 가중치를 10으로 갱신하게 되고 Cloud 에 포함시킵니다.

 

 

이제 2번 정점에서 갈 수 있는 경로를 봐야하는데 뭔가 이상합니다. 음수인 경로를 가지고 있어 시작 정점이었던 1번 정점이 가지고 있던 0이라는 값보다 더 작은 -1이라는 값을 넣을 수 있게 되는 것이죠. 경로를 확정했음에도 불구하고 가중치를 갱신을 할 수가 있게 됩니다. 다익스트라 알고리즘이 완전 깨지게 되는 것이죠. 다익스트라는 한 번 경로를 확정한 정점에 대해서 다시는 갱신이 일어나지 않습니다.

 

위와 같은 상황이면 1번 정점과 2번 정점 사이를 왔다갔다 할때마다 음수값이 점점 더 작아지게 되어 최단 경로의 가중치는 계속해서 갱신되게 됩니다. 무한 루프 상황입니다.

 

 

(2) 탐색할 수 없는 경로

 

 

 

 

위와 같은 음수 간선이 있는 그래프에서 A 정점에서 F번 정점으로 가는 경로를 생각해봅시다. 처음에 A번정점에서 갈 수 있는 곳중 B 정점이 가장 최솟값이므로 B 정점이 Cloud에 속하게 됩니다. B 정점을 경로 확정합니다.

 

 

 

 

 

B 정점을 클라우드에 넣어 놓고 다시 가장 작은 에지를 탐색해보면 D 정점으로 갈 때 2만큼의 값으로 갈 수 있다는 것을 확인할 수 있습니다.

 

이제 D 정점으로 가보죠.

 

 

 

 이제 마지막으로 F 정점으로 3만큼의 값으로 갈 수 있는 게 최소 경로 이므로 F로 이동하고 최단 거리를 확정합니다.

 

 

 

 

 

 

다익스트라 알고리즘으로 최단 경로를 찾고보니 정말 이상한 현상이 발생했습니다. A->B->D->E->F 로 갔을 시에 -94의 가중치로 갈 수 있는데 다익스트라 알고리즘은 그 경로를 찾지 못한 것이죠.

 

 

 

 

이처럼 다익스트라 알고리즘에 음수 가중치가 있을 시에 탐색할 수 없는 경로가 존재하게 됩니다.