- 현재 경유지
- 이미 경유지
- 짧아진 쌍
- 경로
플로이드-워셜 알고리즘
모든 마을에서 다른 모든 마을까지 얼마나 멀까요? 플로이드-워셜 알고리즘은 표 하나와 삼중 반복문으로 한 번에 답합니다. 라운드마다 노드 하나를 경유지로 더 허용하고, 모든 쌍에 대해 그 노드를 거쳐 돌아가는 길이 더 짧은지 묻습니다. 단계별로 진행하며 표가 채워지고 거리가 줄어드는 모습을 보세요. 재생을 눌러 표가 채워지는 모습을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 표에는 지금까지 찾은 모든 노드 쌍 사이의 최단 거리가 들어 있고, 각 간선의 숫자는 그 길이입니다. 라운드마다 노드 하나를 경유지로 더 허용하며, 각 단계는 그 노드를 거쳐 짧아지는 쌍을 보여 줍니다. 노드를 클릭하면 시작 노드가 됩니다. 클릭을 목표로 바꾸고 다른 노드를 클릭하면 마지막에 두 노드 사이의 최단 경로를 볼 수 있습니다. 새 그래프는 다른 그래프를 만듭니다. 노드와 간선 수를 고를 수 있습니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.
작동 원리
- 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다.
- 표를 지켜보세요. 현재 경유지의 행과 열에 색이 칠해지고, 단계마다 더 짧은 거리가 적힙니다.
- 시작과 목표를 고르면 마지막에 둘 사이의 최단 경로를 볼 수 있습니다. 새 그래프로 다른 그래프를 시도할 수 있습니다.
플로이드-워셜 알고리즘의 작동 방식
노드마다 행 하나와 열 하나가 있는 표를 만듭니다. 대각선에는 0, 두 노드가 간선으로 이어진 곳에는 그 간선의 길이, 나머지에는 무한대를 적습니다. 그런 다음 각 노드 k를 차례로 경유지 후보로 삼습니다. 모든 쌍 i, j에 대해 표의 i에서 j까지 거리와, i에서 k까지 거리에 k에서 j까지 거리를 더한 값을 비교해 더 작은 쪽을 남깁니다. 마지막 노드까지 마치면 모든 칸이 두 노드 사이의 최단 거리가 됩니다.
왜 맞을까
k 라운드가 끝나면 표에는 모든 쌍에 대해, 경유지가 모두 지금까지 처리한 노드인 최단 경로가 들어 있습니다. 다음 노드의 라운드는 그 노드가 도움이 되는지만 판단하면 됩니다. 그 노드를 거치는 최단 경로는 그 노드까지의 최단 경로에 그 노드에서의 최단 경로를 더한 것이고, 둘 다 이미 표에 있습니다. 이미 구한 작은 답으로 큰 답을 만드는 이런 방법을 동적 계획법이라고 합니다. 음수 간선이 있어도 작동하며, 대각선에 음수가 나타나면 음수 사이클이 있다는 뜻입니다.
자주 묻는 질문
플로이드-워셜 알고리즘이란?
가중 그래프에서 모든 노드 쌍 사이의 최단 거리를 찾는 알고리즘입니다. 거리 표를 유지하면서 각 노드를 차례로, 그 노드를 거치면 어떤 쌍이 짧아지는지 확인합니다.
플로이드-워셜 알고리즘은 얼마나 빠른가요?
n개 노드에 대한 삼중 반복문이므로 작업량은 n³에 비례해 늘고, 표에는 n²개의 칸이 필요합니다. 노드가 수백 개인 그래프라면 충분합니다. 큰 희소 그래프에서는 모든 노드에서 다익스트라 알고리즘을 실행하는 편이 더 빠릅니다.
플로이드-워셜 알고리즘은 음수 간선을 다룰 수 있나요?
네, 음수 사이클만 없다면 가능합니다. 음수 사이클이 있으면 대각선의 어떤 칸이 음수가 되며, 플로이드-워셜 알고리즘은 이것으로 음수 사이클을 찾아냅니다.
거리뿐 아니라 경로는 어떻게 얻나요?
i에서 j로 가는 길의 다음 노드를 적는 표를 하나 더 둡니다. 어떤 쌍이 k를 거쳐 짧아질 때마다, i에서 k 쪽으로 가는 다음 노드를 복사합니다. 그 표를 i에서 j까지 따라가면 경로가 나옵니다.
내 그래프가 어딘가로 전송되나요?
아니요. 그래프는 브라우저 안에서 만들어지고 표도 브라우저 안에서 채워지며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동