[JAVA] 백준 11404 - 플로이드
2022. 8. 18. 20:00
JAVA/백준(BOJ) 문제풀이
플로이드-워셜 알고리즘 설명 및 백준 11404번 문제 풀이 https://chb2005.tistory.com/80 [JAVA] 플로이드-워셜 알고리즘 (Floyd-Warshall) Floyd-Warshall 알고리즘 이란? 모든 노드간에 최단거리를 구하는 알고리즘 다익스트라, 벨만포드는 한 노드에서 모든노드까지의 최단경로 Floyd-Warshall은 모든노드에서 모든노드까지의 최단 경로 벨 chb2005.tistory.com
[JAVA] 플로이드-워셜 알고리즘 (Floyd-Warshall)
2022. 6. 5. 20:11
JAVA/알고리즘 개념 정리
Floyd-Warshall 알고리즘 이란? 모든 노드간에 최단거리를 구하는 알고리즘 다익스트라, 벨만포드는 한 노드에서 모든노드까지의 최단경로 Floyd-Warshall은 모든노드에서 모든노드까지의 최단 경로 벨만포드와 같이 가중치에 음수가 있어도 가능 시간복잡도 : O(V^3) (V:노드의 수) 위 그래프에서 1 -> 5의 최단경로는 1 -> 3 -> 4 -> 5 임 이 때, 중간지점을 4로 지정해 보면 (1 -> 4) + (4 -> 5) = 1 -> 5 가 항상 성립 Floyd-Warshall은 이 논리를 사용 시작점 : s, 끝점 : e, 중간점 : k => dist[s][e] = min(dist[s][e], dist[s][k] + dist[k][e]) k, s, e는 3중 for문을 통해 모든 경..