이런 그래프에서 1에서 5까지 가는 경우를 생각해보면
플로이드 와샬은 이런 경우에 유용함!
코드 형태
func floydWarshall() {
for i in 0..<N {
for j in 0..<N {
for k in 0..<N {
node[j][k] = min(node[j][i] + node[i][k], node[j][k])
}
}
}
}
이런 식으로 플로이드 와샬은 시작 : 1...n 중간: 1... n 도착: 1...n 까지 n의 3제곱으로 모든 경우의 수를 탐색하는 것
핵심은 위와 같이 현재 값인 [j][k]값과 [j][i] + [i][k] 값 중 작은 값을 저장하는 것, 마치 DP 처럼!
여기서 [j][k]라는 뜻은 j 정점으로부터 k 정점 까지의 거리라는 뜻
참고: https://fomaios.tistory.com/entry/Algorithm-플로이드-와샬Floyd-Warshall-이란