플로이드-워셜 알고리즘은 그래프의 모든 정점 간의 최단 거리를 찾는 알고리즘이다. 주로 그래프를 인접행렬로 표현한 상태에서 많이 쓰이는 방법이다. 양방향 그래프와 방향 그래프 모두 적용할 수 있으며 음수 가중치를 허용한다. 플로이드-워셜 알고리즘은 어떠한 두 정점 간의 최단 경로를 그 경로의 속한 두 최단 경로의 합으로 생각하는 데서 출발한다.
원리
어떠한 두 정점 와 사이의 최단 경로가 다음과 같이 정점 를 경유한다고 가정하자.
다이어그램을 그리는 중..
위 그림에서 정점 와 사이의 최단 경로는 정점 와 , 정점 와 의 최단 경로의 합이라고 생각할 수 있다. 또한 정점 와 사이의 최단 경로는 방금처럼 그사이의 어떤 정점에 접하는 두 최단 경로의 합으로 생각할 수 있고, 이러한 재귀적인 생각은 두 정점 사이의 경로에 경유하는 정점이 없어질 때까지(즉 두 정점이 직접 연결될 때까지) 반복할 수 있을 것이다. 이를 반대로 생각하면 모든 정점의 직접 연결 정보, 즉 인접행렬을 가지고 모든 정점 사이의 최단 경로를 구하는 알고리즘을 생각해 볼 수 있다. 먼저 다음과 같은 그래프가 있고 이를 인접행렬 로 표현했다고 가정하자.
다이어그램을 그리는 중..
연결되어 있지 않은 정점들 간의 거리는 무한으로 초기화한다. 우선 정점 를 중간 정점로서 경유하는 것부터 생각해보자. 정점 와 는 직접 가는 것보다 정점 를 경유하는 것이 더 거리가 짧다. 즉, 다음을 만족한다.
따라서 와 을 수정해 다음과 같이 를 중간 정점로 사용했을 때의 최단 거리 표인 을 얻는다.
는 다른 말로 하면 이 그래프 상에서 를 중간 정점로 사용할 수 있을 때의 최단 거리표이다. 여기서 추가로 정점 를 중간 정점로 사용하겠다고 선언하자. 우리의 목표는 와 를 중간 정점로 사용할 수 있을 때의 최단 거리표 를 구하는 것이다. 정점 는 정점 를 통해서 와 에 닿을 수 있다. 우리는 앞서 를 구해놓았으며 는 와 의 경로가 를 경유하면 더 빨라진다는 사실을 담고 있다. 따라서 정점 에서 를 갈 때 를 참고하여 경로 대신 를 거쳐 가는 더 빠른 경로를 얻을 수 있다. 즉, 를 구할 때는 이전에 구해놓았던 을 사용하면 된다는 것을 직관적으로 알 수 있다.
위의 논리를 계속해서 반복해 로부터 를 얻을 수 있고, 로부터 를 얻을 수 있다. (실제로 구해보면 갱신될 것이 없으므로 위의 표와 동일하게 나올 것이다.) 는 그래프 상의 모든 정점을 중간 정점로 사용할 수 있다는 뜻이므로 결국 이 그래프 상의 궁극적인 최단 거리표가 될 것이다.
구현
플로이드-워셜의 구현은 굉장히 아름답다. 단순한 3중 반복문이면 되기 때문이다. 에서 시작해 중간 정점 을 하나씩 추가하면서 모든 시작점과 종점 쌍 에 대해서 을 거쳐가는 경로()와 기존 경로() 중 어떤 것이 짧은지를 검사해 갱신해주면 된다. 다음은 그것을 간단히 수식으로 나타낸 것이다.
copy deepcopy
() -> [[]]:
result = deepcopy(weight)
m ((weight)):
s ((weight)):
e ((weight)):
result[s][e] = (result[s][e], result[s][m] + result[m][e])
result