플로이드 알고리즘이란? 한 도시에서 다른 도시로 가는 직항로가 없는 경우 가장 빨리 갈 수 있는 항로를 찾는 shortest path 문제들 중 하나이다. 플로이드 알고리즘은 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단 거리를 구한다. 플로이드 알고리즘이 shortest path 문제들 중 한 유형이므로, 플로이드 알고리즘을 살펴보기 전에 shortest path의 특징을 먼저 알아볼 필요가 있다. ① W : 그래프의 인접행렬 W[i][j] = 이음선의 가중치 (vi에서 vj로의 이음선이 있는 경우) = ∞ (vi에서 vj로의 이음선이 없는 경우) = 0 ( i = j인 경우 ) ② D(k) : 각 정점들 사이의 최단거리 (floyd 알고리즘에서 고안) k : 중간에 거쳐갈 수 있는 정점..