플로이드

# 플로이드-워셜 알고리즘 모든 정점 사이의 최단 경로를 구하는 알고리즘 순환만 없다면 음수 가중치도 가능 동적계획법으로 접근 dist[i][j] = Math.min( ~ , ~ ) 형태를 가짐 N개의 정점을 가진다고 할 때, 모든 정점으로 가는 최단 거리를 확인하므로 시간복잡도 = O(N^3) N이 200~300 이하인 경우에만 가능 # 코드 1. INF 값으로 세팅 public static final int INF = 1_000_000_000; INF 값을 Integer.MAX_VALUE로 설정하는 경우, 연산 과정에서 overflow 발생하는 문제 종종 있음 => 잘 확인해서 INF 값 적당히 크게 설정하기 for(int i=1;i