💻CS/알고리즘1 [JAVA] Floyd-Warshall 플로이드-워셜 / 백준 11404 플로이드-워셜(Floyd-Warshall) 알고리즘이란? 가중 그래프에서 최단 거리를 구할 때 사용하는 알고리즘이다 아래 그래프를 보자 2에서 3으로 갈때 가능한 거리는 2 -> 3, 거리 = 3 2 -> 1 -> 3, 거리 = 4 - 2 = 2 최단 거리는 2 -> 1 -> 3 으로 가는 2다 만약 다른 노드 끼리의 거리를 구하려면? 위 그래프는 눈대중으로 바로 알 수 있지만 복잡해질 경우 찾는데 오래걸린다 플로이드-워셜을 이용해 접근해보자 위 이미지에서 k 값은 중간 노드다 k가 0 부터 4까지 값이 있는데 이는 중간 노드가 없을 때, 노드1일 때 노드2일 때 노드3일 때 노드4일 때를 나눠서 두 노드 사이에 중간 노드가 존재할 경우 중간 노드를 거칠 경우와 안걸칠 경우 중 최단 거리를 업데이트 해가.. 2022. 12. 28. 이전 1 다음
