다익스트라는, 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산한다. (출처: 책 알고리즘문제해결전략) 알고리즘 특징 우선순위 큐(파이썬에서는 heapq 사용)에 정점의 번호와 함께 지금까지 찾아낸 해당 정점까지의 최단 거리를 쌍으로 넣는다. 정점까지의 최단거리를 기준으로 정점을 배열함으로써 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾는 과정을 간단하게 한다. 유의할 점은, 각 정점까지의 최단 경로가 갱신될 수 있다는 점이다. 핵심 구조 import heapq g = [[] for _ in range(노드수 + 1)] for _ in range(노드수): 출발노드, 도착노드, 가중치 = map(int, input().split())..