Always Be Wise

플로이드 워셜 알고리즘(Floyed-Warshall Algorithm)은 모든 정점에서 모든 정점 사이의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘이 하나의 정점에서 모든 정점 사이의 최단 경로를 찾는 것과는 차이가 있다. 또한 가중치를 음수와 양수 모두 가질 수 있다는 점도 다르다. 플로이드 워셜 알고리즘의 기본 동작 원리는 다음과 같다. 1. 최단 거리 테이블을 만든다. 이때, 초기 주어진 조건으로 하나의 정점에서 다른 정점으로 바로 갈 수 있는 경우 그 값으로, 갈 수 없는 경우 무한대로 테이블을 초기화한다. 2. 모든 정점에 대하여 해당 정점을 지나 다른 정점으로 이동할 때의 거리를 구하고, 기존의 거리와 비교하여 그 거리가 더 짧다면 테이블의 값을 갱신한다. 점화식으로 표현하자면 다음과..