플로이드 와샬 (Floyd-Warshall)

서론 https://commons.wikimedia.org/wiki/Category:Floyd-Warshall_algorithm?uselang=ko 자주 다익스트라와 함께 언급되는 알고리즘으로, 모든 정점에서 다른 모든 정점까지의 최단 거리를 구할 때 쓴다.

다이나믹 프로그래밍 기법을 사용하기 때문에 그래프를 인접 행렬 방식으로 다룬다. 시간 복잡도는 모든 최단 거리를 구하기 때문에 O(V3).

다익스트라나, 벨만 포드에 비하면 큰 편이다. 다익스트라 플로이드 와샬 벨만 포드 가중치가 양의 정수일 때만 가능.

가중치가 음의 정수일 때도 가능. 가중치가 음의 정수일 때도 가능.

(단, 음의 사이클이 없어야 한다.) 우선순위 큐 사용 시, O(E log V) 3중 For 문이라 O(V^3) O(VE) V는 Vertex (정점), E는 Edge (간선)를 의미함 설명 가중치 인접 행렬에서 distance[i][j]는 i 번째 노드와 j 번째 노드 사이의 직속 거리를 말한다.

가중치 인접 ...