[알고리즘] 다익스트라 최단경로 알고리즘

[간단한 다익스트라 최단 경로 알고리즘]

• 음의 간선이 없을 때 정상적으로 동작한다. 실제로 GPS 소프트웨어의 기본 알고리즘으로 많이 채택된다고 한다.
• 다익스트라는 최단 경로를 다루는 알고리즘이지만 코테에는 최단 거리가 주로 나오기 때문에 일단 최단 거리만을 책에서 다루겠다고 한다.
• 노드 1을 출발점으로 해서 최단 거리를 찾아나간다. 노드 1과 이어진 가장 짧은 간선을 찾는데, 다른 노드까지는 현재 무한으로 초기화 된 상태이다.
• 이미 탐색한 노드를 제외하고, 탐색하지 않은 노드 중 출발지로 부터 거리가 가장 가까운 노드부터 해서 탐색해나가며, 최단 거리를 갱신한다.
• 거리가 최솟값인 지점부터 탐색하기 때문에 이미 탐색한 노드와의 거리는 굳이 갱신할 필요가 없게 된다. ( 빨간색으로 표시 ) => 마지막 노드도 따라서 굳이 탐색할 필요가 없다.
• 간단한 다익스트라 최단 경로 알고리즘은 \( O(V^2) \) 의 시간 복잡도를 갖는다. ( V는 노드 수 )
  최단 거리가 짧은 노드를 매번 검색해야하기 때문이다.
  노드 개수가 5000개 이하라면 괜찮지만 10000개 이상이면 다른 방법을 찾아야 한다.

import sys
input = sys.stdin.readline
INF = int(1e9)     # 1e9는 10억을 의미한다. (거리 초기화)

n, m = map(int,input().split())        # 노드의 갯수, 간선의 갯수
start = int(input())                   # 출발 노드

graph = [[] for _ 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_smalest_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(strat):
    distance[start] = 0        # 자기 자신은 거리가 0
    visited[start] = True      # 시작 노드 방문

    for i in graph[strat]:     # start 노드 주변의 간선
        distance[i[0]] = i[1]
    
    for _ in range(n-1):
        now = get_smalest_node() # 방문하지 않은 최단 거리 짧은 노드
        visited[now] = True      # 방문처리
        for j in graph[now]:
            cost = distance[now] + j[1]    # now 까지 거리 + now에서 뻗은 간선 거리
            distance[j[0]] = min(distance[j[0]],cost)

dijkstra(start)

 

 

 

 

---

[개선된 다익스트라 최단 경로 알고리즘] 

• 최악 경우에도 \( O( ElogV) \) 를 보장 ( V는 노드의 개수, E는 간선의 개수 )
• 단순한 다익스트라 최단 경로 알고리즘의 경우에는 get_smallest_node() 를 통해 매번 최단 거리 테이블을 선형적으로 탐색하였었다. 이 과정에만 \( O(V) \) 의 시간이 걸렸다. 이를 줄이고자 하는게 개선된 다익스트라 최단 경로

 

• Heap 자료구조는 우선 순위 큐를 구현하기 위해 사용하는 자료구조 중 하나.
  ( 우선 순위 큐 : 우선 순위가 가장 높은 데이터를 가장 먼저 삭제 )
• 파이썬에서는 PriorityQueue 혹은 heapq를 사용, heapq가 더 빠르게 동작하기 때문에 수행시간이 제한된 상황에서는 heapq 사용을 권장한다.
• 현재 가장 가까운 노드를 저장하기 위한 목적으로 우선 순위 큐를 추가로 사용한다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# 노드의 갯수, 간선의 갯수
n,m = map(int,input().split())
start = int(input())
graph = [[] for _ in range(n+1)]

# visited 를 사용하지 않는다!
distance = [INF]*(n+1)

for _ in range(m):
    # a번 노드에서 b번 노드로 c만큼 거리
    a, b, c = map(int,input().split())
    graph[a].append((b,c))

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))       # 거리, 노드 힙에 추가
    distance[start] = 0               # 거리에다가도 갱신

    while q:
        dist, now = heapq.heappop(q)

        # 힙에 있는 거리값이 저장되어 있는 거리 값보다도 작다면, 탐색할 필요가 없는 것
        # 따라서 visited가 필요가 없다.
        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)

참고한 책 ; 나동빈 (2020). <이것이 취업을 위한 코딩 테스트다 with 파이썬>. 서울시: 한빛미디어.