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])