[다익스트라, Dijkstra, 구조] 백준 1753. 최단 경로

다익스트라는,

단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산한다. (출처: 책 알고리즘문제해결전략)

알고리즘 특징

• 우선순위 큐(파이썬에서는 heapq 사용)에 정점의 번호와 함께 지금까지 찾아낸 해당 정점까지의 최단 거리를 쌍으로 넣는다.
• 정점까지의 최단거리를 기준으로 정점을 배열함으로써 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾는 과정을 간단하게 한다.
• 유의할 점은, 각 정점까지의 최단 경로가 갱신될 수 있다는 점이다.

핵심 구조

import heapq

g = [[] for _ in range(노드수 + 1)]
for _ in range(노드수):
    출발노드, 도착노드, 가중치 = map(int, input().split())
    g[출발노드].append([가중치, 도착노드])

h = []
dp = [] * (노드수+1)     # dp[노드] = 해당 노드까지의 최단 거리
def Dijkstra(start):

    heapq.heappush(h)   # heapq.heappush(h,[가중치, 도착노드])
    dp[start] = 0

    while h:
        가중치 w, 도착노드 n = heapq.heappop()

        if dp[n] < w:   # 이미 더 짧은 최단 거리가 들어있음
            continue
        for 다음가중치 next_v, 다음노드 next_n in g[n]:
            가중치합 = w + 다음가중치 next_v
            if 가중치합 < dp[next_n]:
                dp[next_n] = 가중치합
                heapq.heappush(h, [가중치합, next_n])


Dijkstra(시작점)
print(dp[목적지 노드])

가중치 = 거리

주요 변수

node_graph
heap
dp
weight, node
next_weight, next_node
sum_weight

관련 문제

백준 1753 최단 경로

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

풀이

import sys
import heapq
input = sys.stdin.readline

v, e = map(int, input().split())
start = int(input())
inf = sys.maxsize
dp = [inf] * (v + 1)

heap = []
graph = [[] for _ in range(v + 1)]


def Dijkstra(start):
    dp[start] = 0

    heapq.heappush(heap, (0, start))
    while heap:
        w, nowNode = heapq.heappop(heap)

        if dp[nowNode] < w:
            continue
        for nextW, nextNode in graph[nowNode]:
            nextW = nextW + w
            if nextW < dp[nextNode]:
                dp[nextNode] = nextW
                heapq.heappush(heap, (nextW, nextNode))


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

Dijkstra(start)
for e in dp[1:]:
    print("INF" if e >= inf else e)