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

Soorim Yoon·2022년 11월 1일

다익스트라

알고리즘 & 코딩테스트

목록 보기

59/67

최단 경로 알고리즘

최단 경로 알고리즘 (Shortest Path Algorithm)은 가장 짧은 경로를 찾는 알고리즘이다. '길 찾기' 문제에서 주로 사용되며 여러 종류의 최단 경로 알고리즘이 존재한다.

✏️ 최단 경로 알고리즘의 종류

1) 다익스트라 알고리즘
2) 플로이드 워셜 알고리즘
3) 벨만 포드 알고리즘

이 중에서 다익스트라 최단경로 알고리즘과 플로이드 워셜에 대해 공부해보고자 한다. 본 게시글에서는 다익스트라 최단경로 알고리즘의 소스 코드 구현해 대해 설명하고자 한다.

다익스트라 알고리즘 구현

heapq를 사용한 개선된 다익스트라 알고리즘을 구현하였다.

✏️ 필요 인자 설명

1) graph : 이차원 리스트로 (node, cost) 형태의 값이 저장된다. graph 리스트의 각 인덱스 번호에 해당하는 노드가 연결된 모든 노드의 정보들을 저장한다.
2) distance : 일차원 리스트로 start 노드부터 distance 리스트의 각 인덱스 번호의 노드까지 이동 중인 최단 경로를 기록한다.
distance 배열의 값을 갱신하는 과정에서, distance 배열에 저장된 값과 현재 노드를 거친 비용을 비교한다. 이때 distance 배열에 저장된 값이 더 작은 상태라면 값을 갱신하지 않고, 더 큰 상태라면 현재의 cost 값으로 배열을 갱신한다.
3) n, m start
n : 총 노드의 개수, m : 총 간선의 개수, start : 시작 노드

소스코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)      # 무한을 의미하는 값으로 10억을 설정

# 1) 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())

# 2) 시작 노드 번호 입력받기
start = int(input())

# 3) 각 노드에 연결된 노드 정보를 담는 리스트
graph = [[] for _ in range(n+1)]

# 4) 최단거리 테이블을 무한으로 초기화
distance = [INF]*(n+1)

# 모든 간선 정보 입력 받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # c : a번 노드 -> b번 노드로 가는 비용
    graph[a].append((b, c))       # 양방향인 경우 모두 추가해주기 -> graph[b].append(a, c)

def dijkstra(start):
    queue = []
    # 시작노드(자기 자신)로 가는 비용인 0을 큐에 삽입
    heapq.heappush(queue, (0, start))       # 비용(0), 노드(시작)
    distance[start] = 0						# 시작 지점의 최단경로는 0으로 초기화한다 (중요!)
    # 시작 지점의 최단 경로를 0으로 초기화하지 않는 경우, 시작 지점의 distance 배열 값이 10억(1e9)이 됨

    while queue:        # 큐가 비어있지 않다면
        # 가장 최단 거리가 짧은 노드 정보 꺼내기
        dist, now = heapq.heappop(queue)         # 비용, 노드번호를 현재 값으로 갱신
        # 현재 노드가 이미 처리된 적이 있다면 무시 (최단거리 테이블에 저장된 값이 더 작다면 continue)
        if distance[now] < dist:        # 현재 노드의 최단거리 테이블 값 < 현재 노드의 비용
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:        # i는 (node, dist) 꼴
            cost = dist + i[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if distance[i[0]] > cost:       # 새로 계산한 cost 비용이 더 작으면
                distance[i[0]] = cost       # 최단거리 값을 갱신
                heapq.heappush(queue, (cost, i[0]))

# 다익스트라 알고리즘을 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력 (start 노드에서 각 노드들로 가기 위한 최소비용)
for i in range(1, n+1):
    # 도달할 수 없는 경우, 값으로 무한을 출력
    if distance[i] == INF:
        print("INF")
    # 도달할 수 있는 경우, 최단거리를 출력
    else:
        print(distance[i])

주석 없는 소스코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)      

n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n+1)]
distance = [INF]*(n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))       

def dijkstra(start):
    queue = []
    heapq.heappush(queue, (0, start))      
    distance[start] = 0

    while queue:        
        dist, now = heapq.heappop(queue)        
        if distance[now] < dist:        
            continue
        for i in graph[now]:        
            cost = dist + i[1]
            if distance[i[0]] > cost:       
                distance[i[0]] = cost       
                heapq.heappush(queue, (cost, i[0]))

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])