플로이드 워셜 알고리즘(Floyd-Warshall)

플로이드 워셜 알고리즘(Floyd-Warshall)

All-pairs 문제

그래프에서 모든 정점 사이의 최단경로 및 최단거리를 구하는 알고리즘

동적계획법 접근으로, 그래프 상의 모든 두 정점을 잇는 경로의 최단거리를 구한다.

여기에 경유지를 기록하면 최단거리 경로까지 구할 수있다.

- 두 정점을 잇는 최소 비용 경로는 경유지를 거치거나 거치지 않는 경로 중 하나에 속한다.

- 만약 경유지를 거친다면 그것을 이루는 부분 경로 역시 최소 비용 경로여야 한다.

음수사이클이 없는 그래프라면 음수 가중치가 있어도 동작