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

다익스트라(Dijkstra) 최단 경로 알고리즘이란?

• 다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때,
• 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다.
  • ‘음의 간선'이 없을 때 정상적으로 동작합니다.
  • 물론, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로,
  • 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 합니다.
• 다익스트라 최단 경로 알고리즘은 그리디 기반입니다.
  • 그리디
    • 매번 ‘가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복합니다.

구체적인 동작 과정

1. 출발 노드를 설정한 뒤, 방문합니다.
2. 최단 거리 배열을 초기화합니다.
3. 아직 방문하지 않은 전체 노드들 중에서, 최단 거리가 가장 짧은 노드를 선택한 뒤 방문합니다.
4. 출발 노드에서 현재 노드를 거쳐 다른 노드까지 가는 거리와, 기존의 출발 노드에서 다른 노드까지 가는 거리를 비교해, 최단 거리 배열을 업데이트합니다.
5. 위 과정에서 3번(방문)과 4번(업데이트)을 반복합니다.

추가 특징

• 다익스트라 알고리즘은, 최단 경로를 구하는 과정에서 ‘각 노드에 대한 현재까지의 최단 거리' 정보를
• 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있습니다.

예제 1

• 출발 노드를 1번 노드로 정해, 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구해보겠습니다.

  

• 우선, 1번 노드와 인접한 노드들을 기반으로 최단 거리 배열을 초기화합니다.

  

  • 경로 1 → 2 의 비용은 3
  • 경로 1 → 3 의 비용은 6
  • 경로 1 → 4 의 비용은 7

• 이후, 아직 방문하지 않은 노드들 중, 가장 최단 거리 비용이 적은 2번 노드를 방문합니다.

  

• 이후, 2번 노드와 인접하며, 아직 방문하지 않은 노드들을 확인하며, 최단 거리 배열을 업데이트합니다.

  • 예를 들어, 기존 1 → 3 의 최소 비용은 6 이고, 1 → 2 → 3 의 비용은 4 이므로,
  • 1 → 3 의 최소 비용은 4 로 업데이트합니다.

• 해당 과정을 반복하며, 최단 거리 배열을 계속해서 갱신해 나갑니다.

예제 2

• 출발 노드를 1번 노드로 정해, 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구해보겠습니다.

  

• 출발 노드를 기준으로, 출발 노드와 각 노드 간의 비용을 2차원 배열로 저장합니다.

  

  • 1행 3열의 값이 5 라는 것은, 1번 노드에서 3번 노드로 가는 비용이 5 라는 것입니다.
  • 1행 5열의 값이 무한 이라는 것은, 1번 노드에서 5번 노드로 바로 가는 선이 없다는 것을 의미합니다.

• 우선, 1 번 노드를 방문합니다.

  

• 1번 노드와 인접한 노드들을 기반으로 최단 거리 배열을 초기화합니다.

  

• 아직 방문하지 않은 노드 중에서, 가장 비용이 적은 4번 노드를 방문합니다.

  

• 4번 노드와 연결되어 있으며, 아직 방문하지 않은 노드들의 최단 거리 비용을 업데이트합니다.

  

  • 4번 노드와 연결되어 있으며, 아직 방문 되지 않은 노드는 2번, 3번, 5번 노드입니다.
  • 기존의 1번 노드에서 2번, 3번, 5번 노드로 가는 최소 비용과,
  • 1번 노드에서 4번 노드를 거쳐 2번, 3번, 5번 노드로 가는 비용을 비교합니다.
    • 기존 1 → 2 의 최소 비용은 2 이지만, 1 → 4 → 2 의 비용은 3 이므로, 그대로 유지합니다.
    • 기존 1 → 3 의 최소 비용은 5 이지만, 1 → 4 → 3 의 비용은 4 이므로, 4 로 변경합니다.
    • 기존 1 → 5 의 최소 비용은 무한이지만, 1 → 4 → 5 의 비용은 2 이므로, 2 로 변경합니다.

• 아직 방문하지 않은 노드 중에서, 가장 비용이 적은 2번 노드를 방문합니다.

  

• 2번 노드와 연결되어 있으며, 아직 방문하지 않은 노드들의 최단 거리 비용을 업데이트합니다.

  

  • 2번 노드와 연결되어 있으며, 아직 방문 되지 않은 노드는 3번 노드입니다.
  • 기존의 1번 노드에서 3번 노드로 가는 최소 비용과,
  • 1번 노드에서 2번 노드를 거쳐 3번 노드로 가는 비용을 비교합니다.
    • 기존 1 → 3 의 최소 비용은 4 이지만, 1 → 2 → 3 의 최소 비용은 6 이므로, 그대로 유지합니다.

• 아직 방문하지 않은 노드 중에서, 가장 비용이 적은 5번 노드를 방문합니다.

  

• 5번 노드와 연결되어 있으며, 아직 방문하지 않은 노드들의 최단 거리 비용을 업데이트합니다.

  

  • 5번 노드와 연결되어 있으며, 아직 방문 되지 않은 노드는 3번, 6번 노드입니다.
  • 기존의 1번 노드로부터 3번, 6번 노드로 가는 최소 비용과,
  • 1번 노드에서 5번 노드를 거쳐 3번, 6번 노드로 가는 비용을 비교합니다.
    • 기존 1 → 3 의 최소 비용은 4 이지만, 1 → 5 → 3 의 비용은 3 이므로, 3 으로 변경합니다.
    • 기존 1 → 6 의 최소 비용은 무한이지만, 1 → 5 → 6 의 비용은 4 이므로, 4 로 변경합니다.

• 아직 방문하지 않은 노드 중에서, 가장 비용이 적은 3번 노드를 방문합니다.

  

• 3번 노드와 연결되어 있으며 아직 방문하지 않은 노드들의 최단 거리 비용을 업데이트합니다.

  

  • 3번 노드와 연결되어 있으며, 아직 방문 되지 않은 노드는 6번 노드입니다.
  • 기존의 1번 노드로부터 6번 노드로 가는 최소 비용과,
  • 1번 노드에서 3번 노드를 거쳐 6번 노드로 가는 비용을 비교합니다.
    • 기존 1 → 6 의 최소 비용은 4 이지만, 1 → 3 → 6 의 비용은 8 이므로, 그대로 유지합니다.

• 아직 방문하지 않은 노드 중에서, 가장 비용이 적은 6번 노드를 방문합니다.

  

• 아직 방문하지 않은 노드는 없으므로, 종료합니다.

• 따라서, 최종 배열은 아래와 같습니다.

  

시간 복잡도

• 다익스트라 알고리즘을 구현하는 방법은 2가지 입니다.
  • 구현하기 쉽지만 느리게 동작하는 코드
  • 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드
• 간단한 다익스트라 알고리즘
  • 개념
    • 매 단계마다 ‘방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해,
    • 1차원 리스트의 모든 원소를 확인(순차 탐색)하는 방법입니다.
  • 시간 복잡도
    • O(V^2)
    • V는 노드의 개수를 의미합니다.
• 개선된 다익스트라 알고리즘
  • 개념
    • 우선순위 큐 자료구조를 사용해, 최단 거리들을 삽입과 동시에 정렬해둠으로써,
    • 매 단계마다 ‘방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 빠르게 선택’하는 방법입니다.
    • 파이썬에서는 PriorityQueue 혹은 heapq 를 통해 우선순위 큐를 사용할 수 있는데,
    • 두 라이브러리 모두 데이터의 개수가 N개일 때, 하나의 데이터 삽입 및 삭제의 시간 복잡도가 O(logN) 이며,
    • 일반적으로 heapq 가 더 빠르게 동작합니다.
  • 시간 복잡도
    • O(ElogV)
    • V는 노드의 개수, E는 간선의 개수를 의미합니다.
    • 우선순위 큐에서 노드를 하나씩 꺼내서 검사하는 반복문(While)은, 노드의 개수 V 이상의 횟수로는 반복되지 않습니다.
      • 반복문이 시작은 되지만, 꺼낸 노드가 처리된 적이 있는 노드라면 추가적인 작업을 진행하지 않는다는 의미입니다.
    • 또한, V번 반복될 때마다 각각 자신과 연결된 간선들을 모두 확인합니다.
    • 따라서, ‘현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인'하는 총 횟수는, 최대 간선의 개수(E)만큼 수행될 수 있습니다.
    • 즉, 전체 다익스트라 최단 경로 알고리즘은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다고 볼 수 있습니다.
    • 앞에서 말했듯이 우선순위 큐에 N개의 데이터를 모두 넣고, 이후에 모두 빼는 과정의 시간복잡도는 O(NlogN) 입니다.
    • 간단하게 생각하면 다익스트라 알고리즘의 시간 복잡도는 최대 E개의 간선 데이터를 힙에 넣었다가 다시 빼는 것으로 볼 수 있으므로, O(ElogE) 임을 이해할 수 있습니다.
      • 이때 중복 간선을 포함하지 않는 경우, E 는 항상 V^2 보다 작습니다.
      • 왜냐하면, 모든 노드끼리 서로 다 연결되어 있다고 했을 때, 간선의 개수를 약 V^2 으로 볼 수 있고,
      • E 는 항상 V^2 이하이기 때문입니다.
      • 다시 말해, logE 는 logV^2 보다 작습니다.
      • 이때, O(logV^2)는 O(2logV)이고, 이는 O(logV) 입니다.
      • 즉, O(logE) 보다 O(logV) 이 큽니다.
    • 따라서, 다익스트라 알고리즘의 전체 시간 복잡도를 간단히 O(ElogV)라고 볼 수 있습니다.

간단한 다익스트라 알고리즘 코드

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n + 1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1, n + 1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    # 시작 노드를 제외한 전체 n - 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

# 다익스트라 알고리즘을 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

개선된 다익스트라 알고리즘 코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))

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

# 다익스트라 알고리즘을 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

입력 예시

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

출력 예시

0
2
3
1
2
4

참고

• https://m.blog.naver.com/ndb796/221234424646
• 이것이 취업을 위한 코딩 테스트다. with Python