[알고리즘] 다익스트라(백준 1916)

• 시작점에서 종점까지의 최단 경로를 찾는 알고리즘
• 현재까지 가중치 + 추가 가중치 합산이 목적지의 가중치 합산 값보다 작을 때만 갱신한다.
• 간선의 가중치가 음이 아닌 경우에만 사용 가능하다
  • 음의 가중치 : 벨만-포드 알고리즘 사용

백준 1916

리스트 갱신

import sys

input = sys.stdin.readline


def dijkstra(start, end):
    dist = [987654321] * (N + 1)
    dist[start] = 0
    visited = [False] * (N + 1)

    for _ in range(1, N + 1):
        min_idx = -1
        min_value = 987654321

        for i in range(1, N + 1):  # dist 배열에서 visited 안 된 애들 중 가장 작은 노드 찾기
            if not visited[i] and dist[i] < min_value:
                min_idx = i
                min_value = dist[i]  # 갱신

        if min_idx == -1:
            break

        visited[min_idx] = True

        for i in range(1, N + 1):
            if not visited[i] and dist[i] > adj[min_idx][i] + dist[min_idx]:
                dist[i] = adj[min_idx][i] + dist[min_idx]

    return dist[end]


N = int(input())
M = int(input())
adj = [[987654321] * (N + 1) for _ in range(N + 1)]

# 인접행렬 만들기
for _ in range(M):
    start, end, w = map(int, input().split())
    if w < adj[start][end]:  # 여러 간선이 있는 경우 가장 작은 수 선택
        adj[start][end] = w

start, end = map(int, input().split())

print(dijkstra(start, end))

힙큐

import sys
import heapq

input = sys.stdin.readline


def dijkstra(start, end):
    dist = [987654321] * (N + 1)
    visited = set()
    heap = []  # 최소힙 자료구조
    heapq.heappush(heap, (0, start))  # (가중치, 노드번호)

    while heap:
        distance, node = heapq.heappop(heap)
        if node not in visited:
            dist[node] = distance  # 최소힙에서 뽑았으니까 최소 이동 거리가 됨
            visited.add(node)

            for destination in range(N + 1):
                if destination not in visited and dist[destination] > adj[node][destination] + dist[node]:
                    heapq.heappush(heap, (adj[node][destination] + dist[node], destination))

    return dist[end]


N = int(input())
M = int(input())

adj = [[987654321] * (N + 1) for _ in range(N + 1)]

for _ in range(M):
    start, end, w = map(int, input().split())
    if w < adj[start][end]:
        adj[start][end] = w

start, end = map(int, input().split())

print(dijkstra(start, end))