[알고리즘 정리] 다익스트라

다익스트라는 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다.

밑의 그림을 보며 다익스트라 알고리즘에 대하여 알아보겠습니다.

시작점 1을 기준으로, 다른 모든 정점으로 가는 최단 거리는 아래의 표와 같습니다.

한 정점에서 다른 정점으로 가는 경로는 여러가지로 표현될 수 있습니다.

예를 들어, 정점 1에서 정점 4로 가는 경로는 다음과 같은 두 가지 경우가 있습니다.

• 1 → 2 → 4 : 비용 3
• 1 → 4 : 비용 5

따라서 최단 거리를 구하기 위해서는 비용 5가 소모되는 경로가 아닌, 비용 3이 소모되는 경로를 선택해야 합니다.

각 정점으로의 최단 거리는 눈으로 바로 구할 수 있지만, 코드를 사용하면서 더 짧은 거리의 경로를 선택하기 위해서는 각 단계마다 값을 저장해주어야 합니다.

각 정점으로의 최단 거리를 보관하기 위한 1차원 배열이 필요 합니다. 또한 이 배열은 충분히 큰 값으로 초기화 되어야 합니다. 그 이유는, 이동 거리를 비교했을 때 더 작은 값을 선택하기 위함입니다.

가중치 배열을 초기화한 후의 동작 과정은 아래와 같습니다. 순차적으로 값을 갱신시켜 나아가기 위해 큐를 사용합니다.

1. 큐의 맨 앞 요소를 꺼내와 출발지 정점을 선택합니다.
   • 만약, 해당 정점을 방문했다면, 아래 작업들을 건너 뛰고, 다시 1부터 시작합니다.
2. 해당 출발지 정점까지의 최단 거리에 목적지 정점까지의 가중치를 더한 값(1)과, 기존에 구했던 목적지 정점까지의 최단 거리 값(2)을 비교합니다.
   • 만약, (1)이 (2)보다 더 작다면, 해당 거리를 (1)로 변경시켜주고,
   • 큐에 삽입합니다.
3. 1, 2를 반복합니다.

위의 그래프와 동작 과정을 따라 최단 거리를 구해보겠습니다.

시작 정점 1에서 다시 시작점으로는 갈 수 없으니, 해당 거리는 0으로 설정합니다.

큐에 삽입된 시작 정점과 해당 정점까지의 최단 거리 정보를 꺼내옵니다. 정점 1을 방문 처리 합니다.

시작 정점 1에서 갈 수 있는(=이어져 있고, 아직 방문하지 않음) 정점들로는 정점 2, 3, 4가 있습니다.

• 정점 1까지 이동했던 최단 거리(dist[1])인 0과, 목적지 정점 2까지의 가중치인 2를 더한 값인 2
• 정점 2까지 이동했던 최단 거리(dist[2])인 INF

위의 두 값을 비교합니다.

초기에 갈 수 없다고 표시한 infinity 값보다 작으므로 최단 거리를 변경합니다.

갈 수 있는 또 다른 두 정점(3, 4)들도 위 과정을 거칩니다.

따라서 정점 2, 3, 4로의 최단 거리는 각각 2, 3, 5로 변경됩니다.

큐에는 정점 1과 연결된 정점 2, 3, 4로 가는 간선 정보가 들어 있습니다.

다음으로, 우선 순위 큐에 따라 정렬되어 있는 요소들 중 최단거리 값이 가장 작은 맨 앞의 요소를 꺼내옵니다. 정점 2를 방문 처리 합니다.

정점 2를 기준으로 갈 수 있는 정점을 살펴 봅니다. 정점 4로 갈 수 있으며, 그 가중치는 1이 됩니다.

• 정점 2까지 이동했던 최단 거리(dist[2])인 2와, 목적지 정점 4까지의 가중치인 1을 더한 값인 3
• 정점 4까지 이동했던 최단 거리(dist[4])인 5

두 값을 비교합니다.

정점 4로 바로 가는 경로보다, 정점 2를 들러서 가는 경로의 비용이 더 적으므로, 해당 값을 변경시켜 줍니다.

큐에 새로 삽입된 간선 정보를 통해 정점 4로 가는 최단 거리가 5에서 3으로 변경되었음을 알 수 있습니다.

다음으로 우선 순위 큐 맨 앞 요소를 꺼냅니다. 정점 3을 방문 처리 합니다.

정점 3에서 갈 수 있는 정점들은 없으므로, 최단 거리를 갱신하는 과정을 생략합니다.

이제 큐에는 아래의 두 간선 정보만이 존재합니다.

우선 순위 큐의 맨 앞 요소를 꺼내와, 해당 정점을 기준으로 갈 수 있는 정점들을 살펴봅니다. 정점 4를 방문 처리 합니다.

아래 그림을 살펴보면, 정점 4로부터 정점 3으로 비용 3을 소모해 갈 수 있는 것을 알 수 있습니다.

그러면,

• 정점 4까지 이동했던 최단 거리(dist[4])인 3과, 목적지 정점 3까지의 가중치인 4를 더한 값인 7
• 정점 3까지 이동했던 최단 거리(dist[3])인 3

두 값을 비교합니다.

기존의 경로의 거리가 더 작으므로, 값은 변동이 없습니다.

큐에 있는 마지막 요소를 꺼내옵니다. 정점 4는 이미 방문한 기록이 있습니다.

방문한 기록이 있다는 것은, 그 정점까지로의 최단 거리를 이용하여 더 짧은 거리를 구하는 작업을 이미 했다는 것을 의미합니다. 따라서, 거리 비교하는 과정을 생략합니다.

큐가 비어있게 되면, 최단 거리를 구하는 과정이 모두 끝났음을 의미합니다. 계속 더 작은 값으로 갱신시켜 준 dist 배열의 각각의 요소가 해당 정점으로 가는 가장 짧은 거리가 됩니다. 만약 목적지 정점으로의 경로가 존재하지 않는다면, 초기화에 사용된 infinity 값이 남아있게 됩니다.

최악의 경우, 모든 간선 정보들을 우선 순위 큐에 넣게 되므로, O(ElogV)의 시간 복잡도를 가집니다.