플로이드-워셜 시각화
모든 정점 쌍 간 최단 경로를 동적 프로그래밍으로 구하는 과정을 거리 행렬로 학습하세요
그래프★★☆
속도
1 / 1경유 정점 k: - (-1 / 0)
경유 정점 k 갱신됨 선택 경로 음수 간선
경유 정점 k를 하나씩 추가하며 거리 행렬이 갱신되는 과정을 관찰하세요.
경유 정점 k를 하나씩 추가하며 거리 행렬이 갱신되는 과정을 관찰하세요.
플로이드-워셜이란?
모든 정점 쌍(i, j) 간 최단 경로를 O(V³)에 구하는 DP 알고리즘입니다. 경유 정점 k를 하나씩 추가하며 거리 행렬을 갱신합니다.
사용 방법
- 1그래프를 생성하고 실행 버튼을 클릭하세요
- 2경유 정점 k가 증가하며 거리 행렬이 갱신되는 과정을 관찰하세요
- 3갱신된 셀이 하이라이트됩니다
- 4정점 쌍을 선택하면 최단 경로를 그래프에서 확인할 수 있습니다
동작 원리
- 1초기 거리 행렬은 직접 연결된 간선의 가중치, 나머지는 ∞
- 2k = 0, 1, ..., V-1에 대해: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
- 3k번째 반복에서 정점 0~k를 경유지로 사용하는 최단 경로가 구해집니다
- 4대각선 원소가 음수면 음수 사이클이 존재합니다
실무 활용
- •네트워크 라우팅 테이블 계산 (모든 노드 쌍 최단 경로)
- •소셜 네트워크의 관계 거리(Degrees of Separation) 계산
- •교통 시스템의 모든 지점 간 최단 시간 산출
- •그래프의 전이적 폐쇄(Transitive Closure) 계산
비슷한 알고리즘
- •다익스트라 V회 반복 — O(V·E log V), 음수 가중치 불가하지만 희소 그래프에서 빠름
- •벨만-포드 V회 반복 — O(V²·E), 음수 가중치 가능하지만 느림
- •Johnson — 희소 그래프의 모든 쌍 최단경로에 O(V·E log V)로 플로이드보다 빠름
학습 팁
- •4~5개 정점의 작은 그래프부터 행렬 변화를 추적하세요
- •k가 증가할 때마다 어떤 경로가 개선되는지 관찰하세요
- •음수 가중치를 추가하여 음수 사이클 감지를 확인해보세요
자주 묻는 질문
Q. O(V³)이면 느리지 않나?
A. 밀집 그래프에서 모든 쌍 최단경로를 구할 때 가장 간단하고 효율적입니다. 정점 500 이하면 실용적입니다.
Q. 경로 복원은?
A. next[i][j] 행렬을 함께 유지하면 경유 정점을 추적하여 경로를 복원할 수 있습니다.