[Algorithm] 최단 경로 알고리즘(Shortest Paths) - 다익스트라

이번 포스팅의 주제는 최단 경로 알고리즘이다. 그래프 상에서 특정 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘인데, 대표적인 알고리즘으로 오늘 알아볼 다익스트라 알고리즘과, 추후 포스팅 할 예정인 플로이드-워셜 알고리즘, 벨만-포드 알고리즘이 있다. 

 

다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘은 그리디 알고리즘의 한 형태이다. 알고리즘의 진행 과정은 아래와 같다.

1. 초기 distance table의 값을 모두 INF 값으로 설정해 주고, 시작 노드의 값만 0으로 설정한다. 
2. 현재 distance table에서 아직 방문하지 않았으며, 남은 경로 중 가장 경로가 짧은 노드에 대해서 검사를 진행한다.(초기의 경우 시작 노드)
3. 현재 노드와 인접한 노드들을 검사한다. 현재 노드까지의 최단 경로의 길이가 dist이고 edge의 비용을 cost로 가정한다. 이때 인접한 노드까지의 최단 경로, 즉 distance[next_node]와 dist+cost의 값을 비교하여 dist+cost의 값이 더 작다면 distance[next_node]의 값을 dist+cost로 갱신해준다. 
4. 현재 노드에 대한 검사가 모두 끝나면 노드를 방문 처리 한 뒤, 다시 2번 과정으로 돌아간다. 

아래 그림과 함께 이해해보자! 

초기에 distance 배열에서 시작 노드를 제외한 나머지 노드의 값을 모두 INF로 초기화시켜준다. 

현재 distance 배열에서 값이 가장 작은 노드가 시작 노드인 1번이기 때문에, 1번 노드부터 검사를 진행한다. 

1번 노드와 인접한 2번 노드, 4번 노드, 5번 노드에 대해 검사를 진행한다. distance[2]와 distance[4], distance[5] 모두 초기값인 INF로 설정이 되어있고, 이 값은 현재 1번 노드까지의 경로인 0에 각각의 cost인 1과 4를 더한 것보다 크기 때문에 distance[2]와 distance[4]는 1로, distance[5]는 4로 갱신해준다. 마지막으로 1번 노드에 대한 검사가 끝나면 1번 노드를 방문 처리한다.

다음으로 현재까지 경로가 가장 작은 값은 2번과 4번이 모두 1로 동일한데, 이런 경우 노드 번호가 작은 것을 우선으로 검사한다. 따라서 2번 노드에 대해 검사를 진행하게 되고, 현재 5번 노드까지에 대한 경로의 최솟값과 같기때문에 변화는 생기지 않는다.

다음으로 4번 노드를 검사하는데, 인접한 노드인 5번 노드까지의 최단 거리가 3으로 기존 값보다 작기때문에 갱신을 해준다. 

 

위의 과정과 같이 5번 노드에 대해서도 검사를 진행한다. 그 결과 3번 노드와 6번 노드의 최단 거리가 갱신된다.

 

 

 

그 다음으로 경로가 짧은 노드는 3번 노드이기 때문에 3번 노드부터 검사를 진행한다. 이제 7번 노드의 경로가 갱신된 것을 볼 수 있다.

 

 

 

다음으로 최단 거리가 짧은 7번 노드의 검사를 진행한다. 그 결과 6번 노드의 최단 거리가 갱신된 것을 볼 수 있다.

 

이후 6번 노드의 경우 인접한 노드 중 더이상 방문하지 않았던 노드가 없으므로 종료된다. 이렇게 1번 노드로부터 다른 노드까지의 최단 거리를 구할 수 있다. 

 

원래의 다익스트라 알고리즘의 시간복잡도는 $O(V^2)$의 형태로 나타난다. 여기서 $V$는 노드의 개수를 의미한다. 어떤 노드의 검사가 끝나고, 다음 검사할 노드를 찾기 위해서 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택해야 하는데, 이때 시간복잡도가 $O(V)$인 연산을 진행한다. 이 연산을 총 노드의 개수만큼 진행하기 때문에, 다익스트라 알고리즘의 시간복잡도는 $O(V^2)$으로 나타난다. 

이러한 연산을 조금 더 줄이기 위해, 실제로 다익스트라 알고리즘을 구현할 때에는 우선순위 큐를 활용한다. 우선순위 큐를 활용하면 매번 cost가 가장 작은 값을 찾기 위해 선형의 시간 복잡도를 갖는 연산을 진행하지 않아도 된다. 우선순위 큐에는 최대 간선의 총 개수 만큼의 element가 추가될 수 있으며, 이때 최솟값을 찾거나 원소를 삽입하는데 걸리는 시간은 $O(log E)$로 나타난다. 이를 간선의 개수만큼 반복하기 때문에 개선된 다익스트라 알고리즘의 시간복잡도는 $O(Elog E)$이며, 이때 $E < V^2$이므로 $O(Elog E) = O(Elog V)$이다. 따라서 다익스트라 알고리즘의 시간복잡도는 $O(Elog V)$ 라고 할 수 있다. 

 

다익스트라 알고리즘의 경우 그리디 알고리즘을 기반으로 구현되었기 때문에, 이미 한번 검사를 진행한 노드는 더이상 값이 갱신되지 않는다. 따라서 만약 그래프에 음의 간선이 추가되는 경우 다익스트라 알고리즘을 통해 최적해를 구할 수 없다. 이런 경우 벨만-포드 알고리즘을 사용해야한다.

 

개선된 다익스트라 알고리즘의 코드는 아래와 같다. 

import heapq

INF = int(1e9)

def dijkstra(start, graph, distance):
    heap = []
    
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
    heapq.heappush(heap, (0, start)
    distance[start] = 0
    
    while heap: # 큐가 비어있지 않다면
    	# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(heap)
        
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue
        
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for next_cost, next_node in graph[now]:
            cost = dist + next_cost
            if cost < distance[next_node]:
            	distance[next_node] = cost
                heapq.heappush(heap, (cost, next_node))