영주머니의 개발주머니

[알고리즘] 다익스트라 알고리즘 (Dijkstra) 본문

알고리즘/알고리즘 이론

[알고리즘] 다익스트라 알고리즘 (Dijkstra)

영주머니 2023. 7. 5. 15:10

다익스트라 알고리즘은 하나의 출발점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 단, 모든 간선은 음이 아닌 비용을 가진 간선이어야 한다. 

 

기본 예제

 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가

www.acmicpc.net

Python

import sys
import heapq

input = sys.stdin.readline
INF = sys.maxsize

V, E = map(int, input().split())
K = int(input())

dist = [INF]*(V+1)
pq = []
graph = [[] for _ in range(V+1)]

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

def dijkstra(start):
    dist[start] = 0
    heapq.heappush(pq, (0, start))

    while pq:
        weight, node = heapq.heappop(pq)

        if dist[node] < weight:
            continue

        for w, next_node in graph[node]:
            next_w = weight + w
            if next_w < dist[next_node]:
                dist[next_node] = next_w
                heapq.heappush(pq, (next_w, next_node))

dijkstra(K)

for e in dist[1:]:
    if e==sys.maxsize:
        print("INF")
    else:
        print(e)

 

Comments