티스토리 뷰
📌방법 2. 개선된 다익스트라 알고리즘
시간 복잡도: O(ElogV), V=노드의 개수, E=간선의 개수
힙 자료구조 사용
특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있음(로그 시간)
방법 1에서 최단 거리가 가장 짧은 노드를 선택하는 과정을 우선순위 큐를 이용하는 방식으로 대체
📌개선된 다익스트라 알고리즘 소스 코드
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한, 10억
# 노드의 개수, 간선의 개수 입력받기
n, m = map(int, input().split())
# 시작 노드 번호 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 무한으로 초기화
distance = [INF] * (n + 1)
# 모든 간선 정보 입력받기
for _ in range(m):
a, b, c = map(int, input().split()) # a 노드에서 b 노드로 가는 비용 c
graph[a].append((b, c))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
while q: # 큐가 비어있지 않다면
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리된 적 있는 노드라면 무시
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접 노드들 확인
for i in graph[now]:
cost = dist + i[1]
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost # 업데이트
heapq.heappush(q, (cost, i[0]))
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n + 1):
# 도달할 수 없는 경우 무한이라 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리 출력
else:
print(distance[i])
📌참고
'코딩테스트' 카테고리의 다른 글
미래 도시 (3) | 2024.11.06 |
---|---|
최단 경로, 플로이드 워셜 알고리즘 (1) | 2024.11.05 |
최단 경로 (0) | 2024.11.03 |
효율적인 화폐 구성 (1) | 2024.11.01 |
바닥 공사 (3) | 2024.10.31 |