Loading [MathJax]/jax/output/CommonHTML/jax.js

본문 바로가기

Floyd-Warshall

(1)

117. Floyd-Warshall 플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘으로, 그래프의 정점의 수가

$n$ 일 때 시간복잡도는

$\Theta(n^3)$ 이다. 플로이드-와샬 알고리즘은 정점들 사이의 최단 거리를 구할 때 중간에 거칠 수 있는 정점의 수를 늘려 나가면서 최단 거리를 갱신하는 방식으로 작동한다. 벨만-포드 알고리즘이 간선을 확인하는 것과는 약간 다르다. 구체적인 작동 방식은 다음과 같다. 1. 정점

$i$ 로부터 정점

$j$ 까지의 최단 거리를

$d_{i, j}$ 라고 한다. 2. 각각의

$d_{i, j}$ 에 대해

$i = j$ 인 경우

$d_{i, j} = 0$ ,

$i \ne j$ 인 경우

$d_{i, j} = \infty$ 로 초기화한..

티스토리툴바