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

다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단 거리를 구하는 알고리즘이다.
그래프에는 간선마다 가중치가 있으며, 음수는 될 수 없다. (벨만-포드 알고리즘은 음수도 가능)

구현 방법

graph 자료 구조와 우선순위 큐를 사용하며, 아래 과정을 반복함으로써 다익스트라 알고리즘을 구현할 수 있다.
1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점)
2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전의 기록보다 작으면 그 거리를 갱신한다.

코드 구현

• 출발 노드, 도착 노드 설정 (전체 거리를 알고 싶을 때는, 출발 노드만 설정 하여도 무방)
• 알고 있는 모든 거리 값을 부여 (Python에서는 dictionary 객체를 이용하여 graph를 표현)
• 출발 노드부터 시작해 방문하지 않은 인접 노드를 방문하는데, 거리를 계산한 다음 현재 알고있는 거리보다 짧으면 해당 값으로 갱신한다.
• 현재 노드에 인접한 모든 방문 노드까지의 거리를 계산했다면 현재 노드를 미방문 집합에서 제거한다.

예제) 백준 1753번 - 최단경로

import heapq
import sys
input = sys.stdin.readline

def dijkstra():
    global graph, V, E, k
    distance = ["INF" for _ in range(V+1)]
    distance[k] = 0
    q = []
    heapq.heappush(q, (0, k))
    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]:
            continue

        for node in graph[now]:
            v = node[0]
            w = node[1]
            if distance[v] == "INF":
                distance[v] = dist + w
                heapq.heappush(q, (dist + w, v))
            else:    
                if dist + w < distance[v]:
                    distance[v] = dist + w
                    heapq.heappush(q, (dist + w, v))
    for i in distance[1:]:
        print(i)


V, E = map(int, input().split(' '))
k = int(input())
graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split(' '))
    graph[u].append((v, w))

dijkstra()