다익스트라 알고리즘이란 무엇인가?

다익스트라 알고리즘

• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산합니다.
• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 작동합니다.
• 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됩니다.
  - 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하기 때문입니다.

다익스트라 알고리즘 동작 과정

1. 출발 노드를 설정합니다.
2. 최단 거리 테이블을 초기화합니다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택합니다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.
5. 위 과정에서 3, 4번을 반복합니다.

최단 거리 테이블

• 출발노드로부터 '각 노드에 대한 현재까지의 최단 거리' 정보를 1차원 리스트에 저장하며, 갱신됩니다.
• 처음에는 출발 노드의 거리를 0, 나머지 노드의 거리를 INF로 초기화합니다.

간단히 구현한 다익스트라 알고리즘

• 간단히 구현한 다익스트라 알고리즘에서는 매번 최단 테이블에서 최소값을 찾는데,
  이때 순차적으로 순회를 하며 찾습니다.
• [예제 : 이것이 코딩 테스트다]
  
• 출발노드는 1이며, 1에서 갈 수 있는 최단 경로의 노드를 찾으시오

1. 초기 설정

• 출발 노드를 설정합니다. (1)
• 최단거리 테이블을 초기화 합니다.
  - 자신까지의 거리를 0으로, 나머지에 대한 거리는 INF로 초기화합니다.
  • 최단거리 테이블 => [0, 0, INF, INF, INF, INF, INF]

2. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 1번 노드를 처리합니다.

• 1번 노드에서 갈 수 있는 2, 3, 4번 노드에 대한 최단 경로를 갱신합니다.
  • 1 -> 2로 가는 거리 = 0 + 2 < INF 로 2로 갱신됩니다.
  • 1 -> 3로 가는 거리 = 0 + 5 < INF 로 5로 갱신됩니다.
  • 1 -> 4로 가는 거리 = 0 + 1 < INF 로 1로 갱신됩니다.
    @ 최단거리 테이블 => [0, 0, 2, 5, 1, INF, INF] // 0번째는 비워뒀습니다.

3. 방문하지 않은 노드(2, 3, 4, 5, 6) 중에서 최단 거리가 가장 짧은 노드인 4번 노드를 처리합니다.

• 4번 노드에서 갈 수 있는 3, 5번 노드에 대한 최단 경로를 갱신합니다.
  • 현재까지 1에서 4번까지의 최단 경로는 1이므로, 4번 노드를 거쳐서 각 노드로 가는 거리는 다음과 같습니다.
    • 4 -> 3 = 1 + 3 < 5 로 4로 갱신됩니다.
      • 4 -> 5 = 1 + 1 < INF 로 2로 갱신됩니다.
        @ 최단거리 테이블 => [0, 0, 2, 4, 1, 2, INF]

4. 방문하지 않은 노드(2, 3, 5, 6) 중에서 최단 거리가 가장 짧은 노드인 (2, 5)에서 작은 2번 노드를 처리합니다.

• 2번 노드에서 갈 수 있는 3, 4번 노드에 대한 최단 경로를 갱신합니다.
  • 현재까지 1에서 2번까지의 최단 경로는 2이므로, 2번노드를 거쳐서 각 노드로 가는 거리는 다음과 같습니다.
    • 2 -> 3 = 2 + 3 > 4 로 갱신되지 않습니다.
    • 2 -> 4 = 2 + 2 > 1 로 갱신되지 않습니다.
      @ 최단거리 테이블 => [0, 0, 2, 4, 1, 2, INF]

5. 방문하지 않은 노드(3, 5, 6) 중에서 최단거리가 가장 짧은 노드인 5번 노드를 처리합니다.

• 5번 노드에서 갈 수 있는 3, 6번 노드에 대한 최단 경로를 갱신합니다.
  • 현재까지 1에서 5번까지의 최단 경로는 2이므로, 5번노드를 거쳐서 각 노드로 가는 거리는 다음과 같습니다.
    • 5 -> 3 = 2 + 1 < 4 로 3로 갱신됩니다.
    • 5 -> 6 = 2 + 2 < INF 로 4로 갱신됩니다.
      @ 최단거리 테이블 => [0, 0, 2, 3, 1, 2, 4]

6. 방문하지 않은 노드(3, 6) 중에서 최단거리가 가장 짧은 노드인 3번 노드를 처리합니다.

• 3번 노드에서 갈 수 있는 2, 6번 노드에 대한 최단 경로를 갱신합니다.
  • 현재까지 1에서 3번까지의 최단 경로는 3이므로, 3번 노드를 거쳐서 각 노드로 가는 거리는 다음과 같습니다.
    • 3 -> 2 = 3 + 3 > 2 로 갱신되지 않습니다.
    • 3 -> 6 = 3 + 5 > 4 로 갱신되지 않습니다.
      @ 최단거리 테이블 => [0, 0, 2, 3, 1, 2, 4]

7. 방문하지 않은 노드(6) 중에서 최단거리가 가장 짧은 노드인 6번 노드를 처리합니다.

• 6번 노드에서 갈 수 있는 노드가 없으므로, 종료합니다.

[코드]

# 간단히 구현한 다익스트라 알고리즘
import sys
input = sys.stdin.readline
INF = int(1e9)

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

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

print('graph = ', graph)
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
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]:
        # j는 (갈 수 있는 노드, 비용)을 의미
        distance[j[0]] = j[1]
    
    # 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
    for i in range(n - 1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        now = get_smallest_node()
        visited[now] = True

        # key에러를 방지하기 위한 코드
        if now not in graph:
            continue

        # 현재 노드와 연결된 다른 노드를 확인
        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):
    # 도달할 수 없는 경우, 무한이라고 출력
    if distance[i] == INF:
        print('무한')
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

간단히 구현한 다익스트라 알고리즘의 문제점(성능)

• 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형탐색해야합니다.
• 따라서 전체 시간 복잡도는 $O(V^2)$입니다.
• 방문 여부를 확인하는 visited 변수가 있습니다.
• 코딩 테스트에서 전체 노드의 개수가 5,000개 이하라면 사용이 가능하지만, 10,000개를 넘어갈 경우 통과하기 힘듭니다.
  => 우선 순위 큐를 사용하면 어떨까요?

우선순위 큐(Priority Queue)를 사용한 개선된 다익스트라 알고리즘

• 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 이용합니다.
• 최단 거리 테이블이 갱신이 되면 우선순위 큐에 (거리, 노드)를 넣습니다.

1. 초기 설정

• 출발 노드를 설정합니다. (1)
• 최단거리 테이블을 초기화 합니다.
  - 자신까지의 거리를 0으로, 나머지에 대한 거리는 INF로 초기화합니다.
  @ 최단거리 테이블 => [0, 0, INF, INF, INF, INF, INF]
• 우선 순위 큐에 (거리=0, 출발 노드 번호=1)를 삽입합니다.
  (우선 순위 큐를 이용하기에 거리가 작은 값이 우선 순위가 됩니다.)
  @ 우선 순위 큐 = [(0, 1)]

2. 우선 순위 큐에서 원소를 꺼냅니다. 1번 노드는 아직 방문하지 않았으므로 이를 처리합니다.
   • 현재 꺼낸 원소 : (0, 1) // 노드 1번까지의 거리 = 0
   • 1번 노드에서 갈 수 있는 (2, 3, 4)번 노드까지의 거리를 계산합니다.
     • 1 -> 2로 가는 거리 = 0 + 2 < INF 로 2로 갱신되고,
       (거리=2, 노드=2)가 우선순위 큐에 삽입됩니다.
     • 1 -> 3로 가는 거리 = 0 + 5 < INF 로 5로 갱신되고,
       (거리=5, 노드=3)이 우선순위 큐에 삽입됩니다.
     • 1 -> 4로 가는 거리 = 0 + 1 < INF 로 1로 갱신되고,
       (거리=1, 노드=4)가 우선순위 큐에 삽입됩니다.
       
       
       @ 최단거리 테이블 => [0, 0, 2, 5, 1, INF, INF] // 0번째는 비워뒀습니다.
       @ 우선 순위 큐 => [(1, 4), (2, 2), (5, 3)]

3. 우선 순위 큐에서 원소를 꺼냅니다. 4번 노드는 아직 방문하지 않았으므로 이를 처리합니다.
   • 현재 꺼낸 원소 : (1, 4)
   • 4번 노드에서 갈 수 있는 (3, 5)번 노드까지의 거리를 계산합니다.
     • 4 -> 3로 가는 거리 = 1 + 3 < 5 로 4로 갱신되고,
       (거리=4, 노드=3)이 우선순위 큐에 삽입됩니다.
     • 4 -> 5로 가는 거리 = 1 + 1 < INF 로 2로 갱신되고,
       (거리=2, 노드=5)가 우선순위 큐에 삽입됩니다.
       
       
       @ 최단거리 테이블 => [0, 0, 2, 4, 1, 2, INF]
       @ 우선순위 큐 => [(2, 2), (2, 5), (4, 3), (5, 3)]
       

4. 우선 순위 큐에서 원소를 꺼냅니다. 2번 노드는 아직 방문하지 않았으므로 이를 처리합니다.
   • 현재 꺼낸 원소 : (2, 2)
   • 2번 노드에서 갈 수 있는 (4, 3)번 노드까지의 거리를 계산합니다.
     • 2 -> 4로 가는 거리 = 2 + 2 > 1 로 갱신되지 않고, 우선 순위 큐에 삽입하지 않습니다.
     • 2 -> 3로 가는 거리 = 2 + 3 > 4 로 갱신되지 않고, 우선 순위 큐에 삽입하지 않습니다.
       
       
       @ 최단거리 테이블 => [0, 0, 2, 4, 1, 2, INF]
       @ 우선순위 큐 => [(2, 5), (4, 3), (5, 3)]

5. 우선 순위 큐에서 원소를 꺼냅니다. 5번 노드는 아직 방문하지 않았으므로 이를 처리합니다.
   • 현재 꺼낸 원소 : (2, 5)
   • 5번 노드에서 갈 수 있는 (3, 6)번 노드까지의 거리를 계산합니다.
     • 5 -> 3로 가는 거리 = 2 + 1 < 4 로 갱신되고,
       (거리=3, 노드=3)가 우선순위 큐에 삽입됩니다.
     • 5 -> 6로 가는 거리 = 2 + 2 < INF로 갱신되고,
       (거리=4, 노드=6)이 우선순위 큐에 삽입됩니다.
       
       
       @ 최단거리 테이블 => [0, 0, 2, 3, 1, 2, 4]
       @ 우선순위 큐 => [(3, 3), (4, 3), (4, 6), (5, 3)]

6. 우선 순위 큐에서 원소를 꺼냅니다. 3번 노드는 아직 방문하지 않았으므로 이를 처리합니다.
   • 현재 꺼낸 원소 : (3, 3)
   • 3번 노드에서 갈 수 있는 (2, 6)번 노드까지의 거리를 계산합니다.
     • 3 -> 2로 가는 거리 = 3 + 3 > 2 로 갱신되지 않고, 우선순위 큐에 삽입하지 않습니다.
     • 3 -> 6로 가는 거리 = 3 + 5 > 4 로 갱신되지 않고, 우선순위 큐에 삽입하지 않습니다.
       
       
       @ 최단거리 테이블 => [0, 0, 2, 3, 1, 2, 4]
       @ 우선순위 큐 => [(4, 3), (4, 6), (5, 3)]

7. 우선 순위 큐에서 원소를 꺼냅니다. 3번 노드는 이미 방문했으므로 무시합니다.
   (우선 순위 큐를 통해 이미 방문했으면 최소 거리로 계산했음을 의미하기 때문입니다.)

   @ 최단거리 테이블 => [0, 0, 2, 3, 1, 2, 4]
   @ 우선순위 큐 => [(4, 6), (5, 3)]

8. 우선 순위 큐에서 원소를 꺼냅니다. 6번 노드는 아직 방문하지 않았으므로 이를 처리합니다.
   - 현재 꺼낸 원소 : (4, 6)
   - 6번 노드에서 갈 수 있는 노드가 없으므로 패스됩니다.
   @ 최단거리 테이블 => [0, 0, 2, 3, 1, 2, 4]
   @ 우선순위 큐 => [(5, 3)]

   ---

9. 우선 순위 큐에서 원소를 꺼냅니다. 3번 노드는 이미 방문햇으므로 무시합니다.
   @ 최단거리 테이블 => [0, 0, 2, 3, 1, 2, 4]
   @ 우선순위 큐 => []

10. 우선 순위 큐가 비었으므로 끝냅니다.

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

import heapq
V, E = map(int, input().split())
S = int(input())
INF = 1e9 # 무한 설정
distance = [INF]*(V+1) # 최단 거리 테이블
graph = {} # 딕셔너리로 구현

for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u]= graph.get(u, [])
    graph[u].append((v, w))

# 다익스트라
def dijkstra(start):
    q = [] # 힙에 저장되는 값 = (가중치, 노드번호), 우선 순위 큐
    heapq.heappush(q, (0, start)) # 시작, 
    distance[start] = 0 # 시작과 시작의 거리는 0
    while q:
        dist, now = heapq.heappop(q) # 거리가 짧은 노드순으로 정렬됨
        
        if distance[now] < dist or now not in graph:
            # 최단 경로 테이블에 저장되어있는 비용보다 비용이 크거나
            # 마지막 노드일 경우 pass
            continue

        for i in graph[now]: # 현재 노드에 연결되어있는 노드에 대해 반복
            cost = dist + i[1] # i[1]은 i[0]노드로 이동하는 비용을 의미
            if cost < distance[i[0]]: # i[0]는 노드번호, distance[i[0]]는 i[0] 노드에 가는 비용
                # 만약 i[0]로 이동하는 비용이 최단 거리 테이블에 저장되어있는 비용보다 적으면 -> 갱신 및 힙에 추가
                distance[i[0]] = cost # 최단 거리 테이블 갱신
                heapq.heappush(q, (cost, i[0])) # 힙에 (cost, i[0]) 삽입
dijkstra(S)
for i in range(1, V+1): # 모든 노드에 대해 반복
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

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

• 우선 순위 큐를 사용함으로써 최단 거리가 짧은 노드를 선택하는 과정을 스킵했습니다.
• 방문 목적으로 사용되었던 visited 변수가 사용되지 않았습니다.
• 힙 자료구조를 사용하였기에 개선된 다익스트라 알고리즘의 시간복잡도는 $O(E\log{V})$

참고

• 이것이 코딩테스트다