최단거리 : 다익스트라 Dijkstra (Python)

 다익스트라(또는 데이크스트라) 알고리즘은 특정한 시작점에서 다른 모든 점들로 가는 최단거리를 구하는 알고리즘이다.

 그래프 내에서 시작점과 연결되지 않은 노드가 있을 수도 있다. (최단 거리를 구할 수 없는 노드) 이렇게 연결되지 않은 경우를 나타내기 위해 거리를 나타내는 배열 dist = [ ] 의 초기 값을 INF (매우 큰 수)로 설정해주는 것이 일반적이다.

 물론,  여러 간선의 가중치 합이 아무리 커도 INF 보다는 작을 것이라는 제한 조건이 붙어야 한다. 이렇게 구현하면, if dist[node] == INF 일 때, 시작점과 해당 노드가 서로 연결되지 않아서 최단 거리를 구할 수 없다는 뜻이 된다.

 본격적으로 다익스트라 코드를 구현해보자.

 제대로 공부하기 전에 구현된 코드를 복사해서 쓰지 말고, 직접 구현하는 습관을 들여보자! 다음은 내가 다익스트라 코드를 직접 구현하기 전에 적어놓고 참고하는 내용이다.

1. dist 배열을 INF로 초기화 (문제의 가중치 범위, 노드 개수 등을 보고 INF를 적절한 값으로 설정해야 한다. INF를 애매한 값으로 설정하면 중간에 오류가 생길 수 있음)
2. 최단거리를 구하기 위한 우선순위 큐 (min heap) 구현
3. 다익스트라 알고리즘은 특정한 점에서 시작하는 최단거리를 구하는 것임을 기억. start node에 대한 처리가 필요
4. heap에는 (간선 가중치, 노드) 순서대로 heappush 하여, 간선 가중치를 기준으로 min heap이 작동하게 해야 함
5. while heap: 이 오류가 나지 않고 돌아가는지 확인, 중간에 while이 멈추지 않게 노드를 heappush 해주기
6. 현재 노드에서 갈 수 있는 인접 노드를 기준으로 최단거리 update
7. 최단거리를 갱신할 때, 기존 거리 + 새로운 거리 임을 주의하라

 

다음은 대표적인 다익스트라 알고리즘 문제인 백준 1916 - 최소비용 구하기 문제의 정답 코드이다.

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

import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
graph = [[]*(N+1) for i in range(N+1)]

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

#1. dist 배열 초기화 INF
INF = sys.maxsize
dist = [INF] * (N+1)

import heapq as hq
heap = []

#2. 다익스트라는 한 점에서 시작하는 최단거리를 구하는 것임을 기억
start, end = map(int, input().split())

def dijkstra(graph, start):

    dist[start] = 0
    hq.heappush(heap, (0, start)) #힙에는 간선 가중치, 노드 저장

    #3. 현재 노드에서 갈 수 있는 인접 노드를 기준으로 최단거리 update
    while heap:
        distance, node = hq.heappop(heap)

        if dist[node] < distance:
            continue

        for nextNode, newDist in graph[node]:
            alt = distance + newDist #기존 거리 + 새 거리

            if dist[nextNode] > alt:
                dist[nextNode] = alt #최단거리 갱신
                hq.heappush(heap, (dist[nextNode], nextNode))

dijkstra(graph, start)
print(dist[end]) #도착지까지 가는데 드는 최소 비용