최단 경로

1. (개선된) 다익스트라 알고리즘 - 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 - 각 노드에 대한 현재까지의 최단 거리를 계속 갱신 import heapq import sys INF = int(1e9) # n: 노드의 개수 # m: 간선의 개수 # start: 시작 노드의 번호 # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 초기화 graph = [[] for i in range(n+1)] # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n+1) # a, b, c: a번 노드에서 b번 노드로 가는 비용이 c for _ in range(m): graph[a].append((b,c)) def dijkstra(start): q = [] # ..

2021.07.05