플로이드 워셜

[플로이드 워셜 알고리즘] 모든 노드에서 다른 모든 노드 까지 최단 경로를 모두 계산한다. 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없게 됐다. 각 단계마다 \( O(N^2) \) 의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 시간 복잡도는 \( O(V^2) \) 다이나믹 프로그래밍 유형에 속합니다. K 번째 단계에 대한 점화식 : \( D_{ab} = min(D_{ab},D_{ak} + D_{kb} ) \) - A에서 B로가는 최소 비용과, A에서 K를 거쳐 B로 가는 비용 중 더 작은 값으로 갱신 INF = int(1e9) n, m = map(int,input().split()) # 노드의 갯수, 간선의 갯수 graph = [[INF]*(n+1) for _ ..