플로이드 워셜은 다익스트라를 배운 뒤에 만나면 특히 헷갈리기 쉬운 알고리즘입니다. 둘 다 최단거리 문제인데 왜 또 다른 알고리즘이 필요한지, 그리고 왜 갑자기 3중 루프가 등장하는지가 감이 잘 안 올 수 있습니다.
이번 글에서는 플로이드 워셜을 공식 암기가 아니라, 모든 정점 쌍의 거리표를 한 번에 개선해 나가는 방법으로 설명하겠습니다.
다익스트라와 문제 범위가 다르다
다익스트라는 보통 한 시작점에서 다른 모든 정점까지의 최단거리를 구합니다. 즉 한 번 실행하면 한 출발점 기준 결과를 얻습니다.
반면 플로이드 워셜은 모든 i, j 쌍에 대해 최단거리를 구합니다. 즉 “A에서 B”, “A에서 C”, “B에서 D”처럼 전체 관계표를 한 번에 채우는 문제가 핵심입니다. 그래서 둘은 같은 최단거리 알고리즘이지만 바라보는 범위가 다릅니다.
플로이드 워셜은 무엇을 반복할까
핵심은 “중간 정점 k를 하나 허용했을 때 더 짧아지는가”를 보는 것입니다. 즉 i에서 j로 바로 가는 거리와, i에서 k를 거쳐 j로 가는 거리를 비교해 더 짧으면 갱신합니다.
이 과정을 모든 k에 대해 반복하면, 점점 더 많은 중간 정점을 허용한 최단거리표가 완성됩니다. 그래서 3중 루프는 단순한 brute force가 아니라, 허용 가능한 중간 정점을 단계적으로 늘리는 구조라고 보는 편이 정확합니다.
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])이 코드 한 줄이 플로이드 워셜의 본체입니다. dist[i][j]를 직접 갱신하는 대신, i→k→j 경유가 더 짧은지 계속 비교합니다. 그래서 matrix 자체를 계속 개선하는 느낌으로 이해하는 편이 좋습니다.
언제 다익스트라보다 플로이드 워셜이 자연스러울까
문제가 한 출발점이 아니라 모든 출발점에 대한 답을 한 번에 요구할 때, 또는 정점 수가 비교적 작아서 전체 관계표를 다 들고 있어도 되는 경우에는 플로이드 워셜이 자연스럽습니다.
즉 한 쿼리만 빠르게 구하는 것보다, 전체 정점 간 거리 관계를 미리 다 계산해 두는 쪽이 더 유리한 문제에서 잘 맞습니다.
문제에서 어떤 신호가 보이면 플로이드 워셜일까
- 모든 정점 쌍 사이 최단거리
- 정점 수가 비교적 작다
- 여러 출발점에 대한 결과가 한꺼번에 필요하다
- 관계표 전체를 갱신하는 방식이 더 자연스럽다
이 신호가 보이면 다익스트라를 정점마다 여러 번 돌릴지, 플로이드 워셜로 한 번에 풀지 비교해야 합니다. 이 비교 자체가 문제 해결의 핵심이 되는 경우가 많습니다.
헷갈리는 포인트
- 3중 루프는 무작정 모든 경우를 보는 것이 아니라 중간 정점 허용 범위를 늘리는 순서다
- 다익스트라와는 출발점 범위가 다르다
- dist 행렬이 이미 알고리즘의 핵심 상태다
- 전체 관계표가 필요하지 않다면 오히려 다익스트라가 더 자연스러울 수 있다
다익스트라 감각은 다익스트라 글, 그래프 흐름 읽기는 위상 정렬 글과도 연결됩니다.
마무리
플로이드 워셜의 핵심은 3중 루프 자체가 아니라, 중간 정점을 하나씩 허용하며 모든 정점 쌍의 거리표를 갱신하는 데 있습니다.
즉 한 시작점 최단거리인지, 모든 쌍 최단거리인지를 먼저 구분하면 다익스트라와 플로이드 워셜의 경계가 훨씬 선명해집니다.
