#플로이드워셜
질문플로이드워셜 알고리즘의 핵심 원리가 궁금합니다
코딩 테스트를 준비하면서 현재 플로이드 워셜을 공부중입니다 문제는 백준에서 공식외워서 기초 문제는 푸는데, 알고리즘 핵심 원리를 이해 못하니까 하나라도 응용 문제가 나오면 막혀버립니다. 3중 for문의 실행 한번이 d[i,j] = min(d[i,j], d[i,k] + d[k,j]) 즉 k를 경유해서 가는 경로가 더 짧으면, 해당 경로로 갱신한다는건 알겠는데 갱신되어가고(데이터가 변하고) 있는 테이블을 가지고 처음부터 끝까지 순차적으로 순회를 해서 모든 쌍의 최단 경로가 구해지는 원리를 잘 모르겠습니다 유튜브에서 이것저것 봤는데 영 모르겠습니다 ㅠㅠ 혹시 이해시켜주실분 있을까요?
84
1
1
윈비·2024-12-05
매번 테이블을 업데이트한다는 것은 점점 더 나은 최단 경로를 찾아간다는 거예요. 즉, 처음에는 직접 연결된 거리만 알고 시작하는데 한 번씩 경유지를 추가하다보면 새로운 더 짧은 경로를 발견할 수 있죠. 예를 들어, A에서 C로 가는 경로가 처음에는 A -> C로 직접 가는 방법밖에 없었는데, 나중에 A -> E -> C라는 더 ...