플로이드 워셜 알고리즘(1->5) 경우

22.04.10 21:24 작성 조회수 276

i가 1, j가 5, k가 2인경우에

(1,5) 와 (1,2)+(2,5) 가 비교되는 경우가 생기는데

(2,5)의 값 같은경우 이전에 k=1일때 (2->1->5)의 값과는 계산해서 비교해 보았지만

반복문의 순서에 따라 k가 2,3,4,5 인 경우

즉 (2->3->5), (2->4->5) 이런경우들과 값을 비교해 보지 못하였다고 생각되는데

최솟값이라고 할 수 있는건가요?

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

12. 플로이드-와샬(그래프 최단거리)

강의실 바로가기

답변 1

답변을 작성해보세요.

김태원

2022.04.20

안녕하세요^^

다이나믹 방법이리 해당 경우가 이미 그 전에 비교되어 현재 값이 내포되어 있습니다.