Floyd2 플로이드 와샬 (Floyd Warshall) 플로이드 와샬 역시 벨만 포드나 다익스트라와 같은 최단 경로 찾기 알고리즘입니다. 다만, 1:N 최단 경로를 찾는 벨만 포드와 다익스트라와 달리, 플로이드 와샬은 N:N 사이의 최단 경로를 찾습니다. 그렇기 때문에 비용을 저장하는 배열로 이중 배열을 사용하게 됩니다. 순환만 발생하지 않는다면 음수 가중치도 가능하며, 기본적으로 동적계획법으로 접근하게 됩니다. 플로이드 와샬은 가능한 모든 경유지에 대해 모든 정점에서 모든 정점으로 가는 최단거리를 확인하기 때문에, 시간복잡도는 O(N^3)이 나옵니다. 역시 n:n 경로라 그런가 다른 알고리즘들보다 시간이 많이 걸리네요ㅎ.. 먼저 플로이드 와샬을 구현하기 위해서 좀 복잡하지만 아래와 같은 그래프를 사용하겠습니다. 그래도 보는사람 쉽게 보시라고 제가 색도 다르.. 2021. 3. 23. [플로이드와샬] 백준 11404번 플로이드 (Java) 백준 11404 : https://www.acmicpc.net/problem/11404 정말 기본 플로이드 와샬 알고리즘 그대로 사용하는 문제이다. 그래서 플로이드 와샬 알고리즘을 공부하면서 풀어보았다. 플로이드 와샬은 다대다 최단거리를 계산할 때 사용한다. 그만큼 속도가 느리지만, 모든 노드 사이의 최단 거리를 알아야 하는 문제에 사용한다. 그럼 어떻게 푸는지 한 번 살펴보자. 기본 세팅 N : 노드 개수 dp[N][N] : 모든 노드 사이의 최단 거리를 저장하는 배열 INF = 최대 거리(나는 N*maxlength로 두었다.) dp 초기화 자기 자신으로 가는 거리는 0 그대로 두고, 나머지는 INF로 설정한다. 예시) 간선 입력 간선을 입력받을 때, 기존 dp값과의 min값으로 저장합니다. 플로이드 .. 2020. 8. 28. 이전 1 다음
