다익스트라 알고리즘이란?

: 그리디 알고리즘 중 하나인 최단경로 탐색 알고리즘

• 특정한 한 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘
• 현재까지 알고 있는 최단거리보다 더 짧은 경로가 나오면 최단경로 테이블 갱신

알고리즘 실행 과정

1. 출발 노드를 지정한다.
2. 최단거리 테이블을 무한으로 초기화한다.(최솟값 비교를 위해)
3. 출발 노드와 연결된 노드들의 최단거리 테이블을 초기화한다.
4. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다.
5. 찾은 노드와 연결된 노드들을 탐색하여 찾은 노드를 거쳐갔을 때 더 짧은 경로가 나오면 최단경로 테이블을 갱신한다.
6. 3~4를 반복한다.

출발노드부터 다른 "모든" 노드까지의 최단거리 테이블을 구할 수 있다.

선형탐색

알고리즘 실행 과정 중 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 매번 선형탐색을 해야 한다. N개의 노드를 N-1번 탐색하니 시간복잡도는 O(N^2)이다. 노드의 개수가 10000개 이상이 되면 시간초과가 나기 쉽다.

선형탐색 다익스트라

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] = 1
    for i in graph[start]:
        distance[i[0]] = i[1] # start와 연결된 노드들을 최단거리 테이블에 초기화
        
    # 한번 확인하면 최단거리가 확정되기 때문에 한번만 탐색하면 된다.
    # 마지막 노드는 다른 테이블이 다 확정되었기 때문에 돌아도 의미없다.
    for i in range(n-1): 
        now = get_smallest_node() # 현재 최단거리가 가장 짧은 노드 찾기
        visited[now] = 1
        for j in graph[now]: # 현재 노드와 연결된 노드들
            cost = distance[now] + j[1] 

            if cost < distance[j[0]]: # 현재 노드를 거쳐 다른 노드로 가는 거리가 더 짧은 경우
                distance[j[0]] = cost  

선형탐색 다익스트라를 사용했을 때 노드의 개수가 많은 경우 메모리초과가 발생할 수 있다

방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 찾는 과정을 heap을 통해 개선할 수 있다.

최소힙

방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 빠르게 찾기 위해 최소힙을 사용할 것이다. cost를 기준으로 오름차순으로 정렬되며 맨 위의 원소는 최단거리가 가장 짧은 노드가 된다.

방문하지 않은 노드는 최단경로 테이블의 값을 통해 체크할 수 있으며 이를 이용하여 개선된 다익스트라 알고리즘의 시간복잡도는 간선의 개수를 E라고 한다면
O(E) + O(ElogE) = O(ElogE) 이다.

힙 다익스트라

https://www.acmicpc.net/problem/1753

import sys
import heapq
input = sys.stdin.readline

v, e = map(int, input().split())
start = int(input())

INF = int(1e9)
distance = [INF for _ in range(v+1)]
graph = [[] for _ in range(v+1)]

for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))


def dijkstra(start):
    queue = []
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    while queue:
        dist, now = heapq.heappop(queue)
		
        # 현재 노드까지 가는 길보다 더 빠른 길이 이미 있는 상태
        if distance[now] < dist:
            continue
		
        # 현재 노드와 연결된 다른 노드를 돌아
        for i in graph[now]:
            next, cost = i[0], i[1]
            # 현재 노드를 거쳐가는 게 더 빠른 경우
            if dist + cost < distance[next]:
                distance[next] = distance[now] + cost
                heapq.heappush(queue, (distance[next], next))


dijkstra(start)

for i in range(1, v+1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])