[Algorithm] 31강 : 플로이드 워셜 알고리즘의 정의와 구현

플로이드 워셜 알고리즘 1.1 플로이드 워셜 알고리즘이란? 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산 플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 겨처 가는 노드를 기준으로 알고리즘을 수행 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않는다 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장 다이나믹 프로그래밍 유형에 속한다 1.2플로이드 워셜 알고리즘 점화식 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인 a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사 1.3 동작과정 초기 상태로 해당 테이블이 만들어지고 경로에 대해 만들어진다. 이 과정을 모든 노드에 적용하여 한다. 1.4 ..