[알고리즘] 다익스트라

다익스트라 최단경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다.

 

다익스트라 알고리즘을 세팅할 때는 다음 단계를 거친다.

1, 주어진값으로 정확하게 그래프를 만들어준다. (양방향성인지 단방향인지, 혹은 최대값이 얼마나 나오는지)

2, 다익스트라 알고리즘을 사용해서 풀어준다.

뭐 이렇게 설명해놨냐고 따질 수 있지만 문제를 풀다보면 이게 전부라는 것을 알 수 있다. 그 다음에 시간 감축은 본인의 자료구조 활용도에 따라 달라지기에 이후는 푸는 사람한테 달려있다.

 

추가로 자료구조 힙을 쓰기에 힙에 대한 이해가 필요하다.

 

INF를 대체로 int(1e9)로 표현해서 10억을 최대값으로 저장해놓는다. 다익스트라는 최단경로를 찾는 문제에 많이 쓰이기에 기본세팅값인 INF가 매우 커야한다. 혹은 sys 라이브러리에서 sys.maxsize를 넣어줘도 좋다.

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

1753번: 최단경로

import heapq
import sys
input = sys.stdin.readline

def dijkstra(start, dis, graph):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))
def solve():
    V, E = map(int, input().split())
    start = int(input())
    INF = 10**9
    dis = [INF]*(V+1)
    graph = [[] for _ in range(V+1)]
    for _ in range(E):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
    dijkstra(start, dis, graph)
    for n in dis[1:]:
        print(n if n != INF else "INF")
solve()