[알고리즘] 다익스트라 알고리즘

본 글은 나동빈 님의 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 참고하여 정리하였습니다.

대표 문제

• 백준 1916번: 최소비용 구하기
• 백준 2665번: 미로 만들기

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

다익스트라 알고리즘은 최단 경로 알고리즘의 하나이다. 그래프의 특정한 노드에서 출발하여 다른 특정한 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. 음의 간선이 있을 때 사이클을 돌면서 비용을 무한대로 줄일 수 있기 때문에 있어서는 안된다. 또한 현실 세계의 길은 음의 간선으로 표현되지 않기 때문에, 다익스트라 알고리즘은 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.

다익스트라 알고리즘은 기본적으로 [[그리디 알고리즘]]으로 분류된다. 항상 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다. 또한 선택사항이지만 매번 '가장 비용이 적은 노드'를 탐색하기 위해 [[우선순위 큐]] 를 사용할 수도 있다.

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.(우선순위 큐)
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3번과 4번을 반복한다.

백준 1916번: 최소비용 구하기 풀이

다익스트라 알고리즘의 기초 문제이다. 우선순위큐에 cost 오름차순으로 노드를 집어넣고, BFS 탐색을 돌면서 최단 거리 테이블 값을 갱신한다.

전체 코드

from heapq import heappush, heappop
import sys
input = sys.stdin.readline
INF = int(1e9)

n = int(input())
m = int(input())
dp = [INF] * n
edges = [[] for _ in range(n)]
for _ in range(m):
    a, b, cost = map(int, input().split())
    edges[a-1].append((cost, b-1))
a, b = map(int, input().split())

dp[a-1] = 0
queue = [(0, a-1)]
while queue:
    curCost, cur = heappop(queue)
    
    if dp[cur] < curCost:
        continue
    
    for nextCost, next in edges[cur]:
        newCost = curCost+nextCost
        if dp[next] > newCost:
            dp[next] = newCost
            heappush(queue, (newCost, next))

print(dp[b-1])