Dijkstra Algorithm

Dijkstra

{{}}
특정 시작점에서 다른 모든 정점으로 가는 최단 거리를 각각 구해주는 알고리즘
{{}}
A도시에서 D도시로 가는 최단 비용(거리, 시간, 돈)을 구하는 문제에 적합한 알고리즘.
⚠️ 음수 가중치 간선이 있는 그래프에서는 쓸 수 없다.

	시간복잡도
우선순위 큐⭕️	O(ElogV)
우선순위 큐❌	O(V^2)

구현

import heapq

INF = int(1e9)

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

    while queue:
        dist, node = heapq.heappop(queue)

        for v, c in graph[node]:
            cost = dist + c
            if cost < distance[v]:
                distance[v] = cost
                heapq.heappush(queue, (cost, v))

"입력 및 실행 코드"

n, m = map(int, input().split()) # 노드, 간선 개수
start = int(input()) # 출발 노드

graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

# 간선 정보
for _ in range(m):
    source, dest, cost = map(int, input().split())
    graph[source].append((dest, cost))

dijkstra(start)

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