[알고리즘] 모든 쌍에 대한 최단 경로 구하기

최단 경로를 구하는 알고리즘을 이용하여 모든 쌍에 대해 최단 경로를 구하도록 코드를 구현해보자 1. Dijkstra 알고리즘 이용 다익스트라 알고리즘은 Greedy 알고리즘을 이용하여 현재 선택된 정점 그래프에서 다음 노드까지의 가중치가 제일 적은 노드를 선택 > MST의 Prim's Algorithm과 유사 MST와 유사하지만 모든 정점을 시작 정점으로 선택하도록 반복해야함 거리와 방문 여부를 체크해야함 > 거리는 그래프 안에서 찾기 import time # 실 실행시간 측정을 위한 타임 모듈 추가 INF=int(1e9) # 무한대 설정 n, m = map(int, input().split()) # 정점의 개수(n), 간선의 개수(m) 입력 graph = [[INF] * n for _ in range(..