[알고리즘] 다익스트라

다익스트라 알고리즘

다익스트라 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발해 다른 노드로 가는 최단 경로를 구해주는 알고리즘이다. 다익스트라 알고리즘은 '음의 간선', 즉 0보다 작은 값을 가지는 간선이 없을 때 정상적으로 동작한다.

다익스트라 알고리즘의 구현 방법에는 2가지가 존재한다.

첫 번째 방법은 순차 탐색을 사용하는 방법이다. 매 단계마다 1개의 노드의 최단 거리를 탐색한다.

두 번째 방법은 우선순위 큐를 사용해 첫 번째 방법에서 시간을 줄인 방법이다.

동작 방법

1. 출발 노드를 설정한다.

2. 최단 거리 테이블을 초기화한다. 본인 노드는 0으로 초기화하고, 그 외 노드는 무한대로 초기화한다.

3. 방문하지 않은 노드 중에서 최단 거리 테이블의 값이 가장 짧은 노드를 선택한다.

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 더 작은 값으로 최단 거리 테이블을 갱신한다.

5. 3, 4번을 반복한다.

순차 탐색을 사용한 다익스트라 알고리즘

아래와 같은 그래프가 존재하고 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구해보자. 최단 거리 테이블을 본인 노드(1)는 0, 나머지 노드들은 무한대로 초기화한다.

최단 경로 테이블 초기화

노드 1과 이어진 노드들은 2번, 6번, 5번 노드이다. 모두 최단 거리가 무한대로 초기화되어 있으므로 노드 1에서 각각의 노드까지의 거리가 최단 경로가 된다.

1번 노드 방문 후 최단 경로 테이블

 

노드 2번과 연결된 노드는 3번, 5번 노드이다.

2번 노드를 거쳐 3번 노드로 가는 거리는 3(2+1)이다. 최단 경로 테이블에는 무한대가 저장되어 있으므로 3으로 최단 경로를 갱신한다.

2번 노드를 거쳐 5번 노드로 가는 거리는 5(2+3)이다. 최단 경로 테이블에는 4가 저장되어 있으므로 최단 경로를 갱신하지 않는다.

2번 노드 방문 후 최단 경로 테이블

3번 노드와 연결된 노드는 4번, 6번 노드이다.

3번 노드를 거쳐 4번 노드로 가는 거리는 4(3+1)이다. 최단 경로 테이블에는 6이 저장되어 있으므로 4로 최단 경로를 갱신한다.

3번 노드를 거쳐 6번 노드로 가는 거리는 8(3+5)이다. 최단 경로 테이블에는 무한대가 저장되어 있으므로 8로 최단 경로를 갱신한다.

3번 노드를 방문 후 최단 경로 테이블

4번 노드와 연결된 노드는 2번, 5번, 6번 노드이다.

2번 노드는 이미 방문한 노드이므로 다시 계산하지 않는다. (이미 방문한 노드는 최단 거리가 저장되어 있다.)

4번 노드를 거쳐 5번 노드로 가는 거리는 6(4+2)이다. 최단 경로 테이블에는 4가 저장되어 있으므로 최단 경로를 갱신하지 않는다.

4번 노드를 거쳐 6번 노드로 가는 거리는 5(4+1)이다. 최단 경로 테이블에는 8이 저장되어 있으므로 5로 최단 경로 테이블을 갱신한다.

4번 노드 방문 후 최단 경로 테이블

5번 노드와 6번 노드와 연결된 노드는 없으므로 탐색을 마친다.

코드

def dijkstra(start):
    # 시작 노드에 대한 거리를 0으로 초기화 및 방문 처리
    distance[start] = 0
    visited[start] = True
    
    # 시작 노드와 연결된 노드까지의 최단 거리 갱신
    for j in graph[start]:
        distance[j[0]] = j[1]

    # 시작 노드를 제외한 노드에 대해서 반복
    for i in range(n-1):
        now = get_smallest_node()
        visited[now] = True
        # 현재 노드와 연결된 노드 확인
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧을 때
            if cost < distance[j[0]]:
                # 최단 경로 갱신
                distance[j[0]] = cost

시간 복잡도

순차 탐색을 사용한 다익스트라 알고리즘은 $O(V)$번에 걸쳐서 최단 거리가 가장 짧은 노드를 탐색하고, 현재 노드와 연결된 노드들을 매번 일일이 확인하는 과정을 거치기 때문에 총 $O(V^2)$의 시간 복잡도를 갖는다.

 

우선순위 큐를 사용한 다익스트라

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 파이썬의 경우 PriorityQueue 혹은 heapq를 사용할 수 있다. 일반적으로 PriorityQueue보다 heapq가 더 빠르게 동작하므로 heapq를 사용하도록 하자. 또한 최소 힙을 기본적으로 이용하므로 최단 거리를 구하는 다익스트라 알고리즘인 경우 우선순위 큐 라이브러리를 그대로 사용하면 된다.

 

아래와 같은 그래프가 존재하고 이를 우선순위 큐를 사용한 다익스트라 알고리즘으로 최단 경로를 구해보자.

시작 노드인 1을 제외한 다른 모든 노드들의 최단 거리 테이블은 무한으로 초기화한다. 또한, 우선순위 큐에 현재 최단 거리 테이블의 최단 거리 중 가장 짧은 1번 노드의 튜플 데이터를 삽입한다.

어떠한 노드를 방문하지 않았을 때 최단 거리 테이블과 우선순위 큐

최소 힙을 사용한 우선순위 큐는 값이 가장 작은 원소가 우선순위 큐의 최상위 원소로 위치해 있다. 따라서 우선순위 큐에서 노드를 꺼낸 후 해당 노드를 이미 방문한 적이 있으면 무시하고 그렇지 않으면 그 노드에 대해서 처리하면 된다.

 

우선순위 큐 최상단에는 1번 노드가 존재한다. 1번 노드는 방문한 적 없는 노드이므로 1번 노드와 연결된 노드와의 거리를 갱신한다.

1번 노드 방문 후 최단 거리 테이블과 우선순위 큐

우선순위 큐의 최상단에는 2번 노드가 위치해있고 2번 노드를 방문한 적이 없으므로 2번 노드와 연결된 노드들을 탐색한다.

2번 노드를 거쳐 3번 노드로 가는 비용은 3(2+1)이다. 최단 거리 테이블에는 무한대가 저장되어있으므로 3으로 최단 거리 테이블을 갱신한다.

2번 노드를 거쳐 5번 노드로 가는 비용은 5(2+3)이다. 최단 거리 테이블에는 4가 저장되어있으므로 최단 거리 테이블을 갱신하지 않는다.

2번 노드 방문 후 최단 거리 테이블과 우선순위 큐

우선순위 큐 최상단에는 3번 노드가 위치해있고 3번 노드를 방문한 적이 없으므로 3번 노드와 연결된 노드들을 탐색한다.

3번 노드를 거쳐 4번 노드로 가는 비용은 4(3+1)이다. 최단 거리 테이블에는 6이 저장되어있으므로 4로 최단 거리 테이블을 갱신한다.

3번 노드를 거쳐 6번 노드로 가는 비용은 8(3+5)이다. 최단 거리 테이블에는 무한대가 저장되어있으므로 8로 최단 거리 테이블을 갱신한다.

3번 노드 방문 후 최단 거리 테이블과 우선순위 큐

우선순위 큐 최상단에는 4번 노드가 위치해있고 4번 노드를 방문한 적이 없으므로 4번 노드와 연결된 노드들을 탐색한다.

4번 노드를 거쳐 2번 노드로 가는 비용은 5(4+1)이다. 최단 거리 테이블에는 4가 저장되어있으므로 최단 거리 테이블을 갱신하지 않는다.

4번 노드를 거쳐 5번 노드로 가는 비용은 6(4+2)이다. 최단 거리 테이블에는 4가 저장되어있으므로 최단 거리 테이블을 갱신하지 않는다.

4번 노드 방문 후 최단 거리 테이블과 우선순위 큐

우선순위 큐에는 5번 노드와 6번 노드가 순서대로 위치해 있지만 연결된 노드가 없으므로 탐색을 종료한다.

5번 노드 방문 후 최단 거리 테이블과 우선순위 큐

 

모든 노드 방문 후 최단 거리 테이블과 우선순위 큐

 

코드

def dijkstra(start):
    q = []
    # 시작 노드의 최단 경로는 0, 큐에 삽입
    heapq.heappush(q, (0, start))
    # 시작 노드의 최단 경로는 0
    distance[start] = 0
    # 큐가 비어있지 않을 때
    while q:
        # 최단 거리가 짧은 노드에 대한 정보
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 노드라면 무시
        # 무한으로 초기화했기 때문
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 노드 확인
        for i in graph[now]:
            #i[1]은 비용 정보
            cost = dist + i[1]
            # 현재 노드를 거친 거리가 더 짧은 경우
            # i[0]은 노드 정보
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

시간 복잡도

파이썬에서 제공하는 PriorityQueue와 heapq는 데이터의 개수가 N개일 때, 하나의 데이터를 삽입 및 삭제할 때의 시간 복잡도는 $O(logN)$이다.

정리

1. 다익스트라 알고리즘은 특정한 노드에서 다른 노드까지의 최단 경로를 구해주는 알고리즘이다.

2. 순차 탐색/ 우선순위 큐를 사용하는 방법 두 가지가 있다.

3. 우선순위 큐를 사용하면 $O(logN)$의 시간 복잡도를 가진다.