백준에서 최단 경로 문제를 풀면서, 아직은 많이 부족한 다익스트라 알고리즘에 대해 공부했다.
다익스트라 알고리즘은 그래프에서 최단 경로를 찾는 데 사용되는 대표적인 알고리즘으로,
본래는 조금 더 복잡했을 코드를 우선순위 큐와 힙 자료구조를 활용하여 좀 더 간단하게 구현 할 수 있다.

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

다익스트라 알고리즘은 '노드와 간선으로 연결된 그래프'에서 '최단 거리'를 찾는 알고리즘이다.
각 간선의 길이(또는 소요 시간)가 다를 때 사용되며, 한 지점에서 다른 모든 지점까지의 최단 경로를 계산할 수 있다.
조금 더 구체적으로 설명하자면 다음과 같다 :

알고리즘의 흐름을 알아보자

알고리즘의 흐름을 1, 2, 3스텝으로 쪼개보자면 다음과 같다.

다익스트라 알고리즘의 구현

다익스틀라 함수를 짜기 전, 기본적으로 필요한 자료는 아래와 같다.

파이썬 코드

여기서, 힙은 튜플도 인자로 받을 수 있다. 이때 튜플의 첫번째 요소를 기준으로 우선순위를 설정한다.
[1] 먼저 아래와 같이 인풋을 입력받아 노드와 간선으로 이루어진 그래프를 생성한다

import heapq
n, m = map(int, input().split()) # n: node, m: edge
start = int(input())

FAR = int(1e9)
graph = [[] for _ in range(n+1)]
minimum_distance = [FAR] * (n+1)

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

[2] 다음으로 출발점을 인풋으로 받는 디익스트라 함수를 정의하면 된다

def dijkstra(start_node):
    distance_table[start_node] = 0
    q = []
    heapq.heappush(q, (0, start_node))

    while q:
        start_here_distance, here = heapq.heappop(q)
        
        if start_here_distance > distance_table[here]:
            continue

        for nearby_distance, nearby_node in graph[here]:
            new_distance = start_distance_here + nearby_distance
            if new_distance < distance_table[nearby_node]:
                distance_table[nearby_node] = new_distance
                heapq.heappush(q, (nearby_distance, nearby_node))