플로이드 와샬(Floydwatershall) 알고리즘 추천 문제
플로이드 와샬이란
모든 정점 에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 거져서 가는 정점들 기준으로 다이나믹 프로그래밍을 기반으로 업데이트 한다. 음수의 좌표에서도 사용이 가능하다.
원소 (i,j) i로부터 j까지의 최단 경로를 저장
점화식 = dp[i][j] = min(dp[i][j],dp[i][n]+dp[n][j])
- n을 거쳐서 가는 경로와 직접 가는 경로를 비교하며 거쳐갈 수 있는 정점들을 모두 비교하여 최단 경로를 업데이트한다.