floyd washall1 [알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm) [알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm) 플로이드 워셜 알고리즘은 edge에서 edge로 이동할 때 최소비용을 구하는 알고리즘이다. 모든 경로의 최소비용을 구할 수 있다. 구현 플로이드 워셜 알고리즘의 구현은 간단하다. k, i, j를 사용하는 3중 for문이 있을 때 3중 for문으로 가장 바깥 k를 사용하는 for문은 edge의 총개수만큼 반복한다. k는 중간에 거쳐가는 edge이다. i는 시작 edge, j는 도착 egde로 사용한다. 현재 비용보다 거쳐가는 비용이 더 적다면 거쳐가는 비용을 사용한다. 자기 자신으로 가는 경로는 0, 도착이 불가능한 경로는 INF(충분히 큰 값)로 표시한다. 이해 구현은 간단하지만 이해는 쉽지 않았다. 플로이드 워셜 알고리.. 2022. 4. 17. 이전 1 다음
