[Python] 다익스트라(Dijkstra) 알고리즘 (최단경로 탐색)

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

정점 - 다른 정점까지의 최단 경로를 구하는 알고리즘
그 과정에 모든 다른 정점까지 최단 경로를 획득

https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

전제 : 모든 간선에 음수인 가중치(weight)가 있어서는 안된다

알고리즘

대략적인 흐름

1. 출발 노드 설정
2. 각 노드로 가는 최소 비용 저장
3. 방문하지 않은 노드 중 비용이 적은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 경우를 계산, 기존 비용보다 낮을 경우 비용 갱신
5. 3~4 반복

구현

1. 초기화:
   1. 시작 정점의 거리 0으로, 나머지의 거리는 무한대(∞)로 설정
   2. 우선순위 큐(최소 힙)에 시작 정점을 넣음
2. 반복:
   1. 우선순위 큐에서 현재 거리가 가장 짧은 정점을 꺼냄
   2. 해당 정점에서 인접 정점으로 가는 간선을~
3. 종료

import sys
import heapq

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

# 노드 수, 간선 수 입력
num_nodes, num_edges = map(int, input().split())
start_node = int(input())
# 그래프 초기화 (인접 리스트)
graph = [[] for _ in range(num_nodes + 1)]
# 시작 시 모든 노드의 최단 거리 INF로 초기화
distances = [INF] * (num_nodes + 1)h

# 간선 정보 입력 (출발 노드, 도착 노드, 가중치)
for _ in range(num_edges):
    src, dest, weight = map(int, input().split())
    graph[src].append((dest, weight))

def dijkstra(start_node):
    priority_queue = []
    heapq.heappush(priority_queue, (0, start_node))
    distances[start_node] = 0
    while priority_queue:
        current_cost, current_node = heapq.heappop(priority_queue)
        # 이미 더 짧은 경로가 존재하는 경우 무시
        if distances[current_node] < current_cost:
            continue

        for adjacent_node, weight in graph[current_node]:
            new_cost = current_cost + weight
            if new_cost < distances[adjacent_node]:
                distances[adjacent_node] = new_cost
                heapq.heappush(priority_queue, (new_cost, adjacent_node))

dijkstra(start_node)

# 결과 출력
for node in range(1, num_nodes + 1):
    if distances[node] == INF:
        print("INFINITY")
    else:
        print(distances[node])

추후 그림자료와 함께 보완 예정