- 현재
- 거리 있음
- 사용한 간선
- 경로
- 음수 사이클
벨만-포드 알고리즘
간선 길이가 음수이면 다익스트라 알고리즘은 망가집니다. 통행료를 받는 대신 돈을 주는 도로 같은 경우죠. 벨만-포드 알고리즘은 그렇지 않습니다. 더 이상 나아지는 것이 없을 때까지 모든 간선을 거듭 확인할 뿐이고, 어떤 사이클 때문에 거리가 끝없이 줄어드는 경우까지 알아챕니다. 노드를 클릭해 거기서 시작하고 패스를 한 단계씩 진행해 보세요. 재생을 눌러 탐색을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 모든 간선은 화살표가 가리키는 쪽으로만 가는 단방향 간선이고, 간선의 숫자는 그 길이이며 음수일 수 있습니다. 노드를 클릭하면 시작 노드가 됩니다. 클릭을 목표로 바꾸고 다른 노드를 클릭하면 마지막에 그 노드까지의 최단 경로를 볼 수 있습니다. 각 노드의 숫자는 지금까지의 거리입니다. 음수 사이클 추가를 체크하면 벨만-포드 알고리즘이 음수 사이클을 찾는 모습을 볼 수 있습니다. 새 그래프는 다른 그래프를 만듭니다. 노드와 간선 수를 고를 수 있습니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.
작동 원리
- 노드를 클릭해 시작 노드로 정합니다. 마지막에 경로를 보려면 클릭을 목표로 바꾸고 다른 노드를 클릭하세요.
- 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다.
- 음수 사이클 추가를 체크하면 벨만-포드 알고리즘이 음수 사이클을 찾는 모습을 볼 수 있습니다. 새 그래프로 다른 그래프를 시도할 수 있습니다.
벨만-포드 알고리즘의 작동 방식
시작 노드에 거리 0을, 다른 모든 노드에 무한대를 줍니다. 그다음 패스를 반복합니다. 각 패스에서 모든 간선 u → v를 한 번씩 확인합니다. u에 거리가 있고 dist(u)에 간선 길이를 더한 값이 dist(v)보다 짧으면 dist(v)를 낮추고, 그곳으로 가는 길로 u를 기억합니다. 패스 k가 끝나면 간선을 k개 이하로 쓰는 최단 경로는 모두 알려집니다. 최단 경로는 각 노드를 많아야 한 번 지나므로 간선이 n − 1개 이하이고, n − 1번의 패스로 항상 충분합니다. 패스 한 번 동안 아무것도 바뀌지 않으면 탐색을 일찍 멈출 수 있습니다.
음수 사이클 찾기
사이클의 간선 합이 0보다 작으면 한 바퀴 더 돌 때마다 경로가 항상 짧아지므로 최단 경로가 아예 없습니다. 벨만-포드는 이를 알아챕니다. n − 1번의 패스 뒤에는 패스를 한 번 더 해도 아무것도 바뀌지 않아야 합니다. 그런데도 완화할 수 있는 간선이 있다면 시작 노드에서 음수 사이클에 도달할 수 있다는 뜻이고, 그 간선에서 기억해 둔 노드를 거꾸로 따라가면 사이클로 들어갑니다. 앱에서는 사이클이 빨간색으로 그려집니다.
자주 묻는 질문
벨만-포드 알고리즘이란 무엇인가요?
간선 길이가 음수일 수 있는 그래프에서 시작 노드 하나로부터 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 패스를 반복하며 모든 간선을 완화하고, 시작 노드에서 음수 사이클에 도달할 수 있으면 이를 알려 줍니다.
다익스트라 알고리즘은 왜 음수 간선에서 실패하나요?
다익스트라는 노드가 큐에서 가장 가까워지는 순간 그 거리를 확정합니다. 나중에 발견한 음수 간선이 더 짧은 길로 그 노드에 돌아올 수 있으므로, 확정된 거리가 틀릴 수 있습니다. 벨만-포드는 거리를 일찍 확정하지 않고 모든 간선을 계속 확인합니다.
왜 n − 1번의 패스인가요?
최단 경로는 한 노드를 두 번 지날 필요가 없으므로 간선이 n − 1개 이하입니다. 패스마다 알려진 최단 경로가 적어도 간선 하나만큼 늘어나므로, n − 1번의 패스 뒤에는 모두 찾게 됩니다.
벨만-포드 알고리즘은 얼마나 빠른가요?
패스마다 간선 E개를 모두 확인하고 패스는 많아야 V − 1번이므로, 작업량은 V × E에 비례해 늘어납니다. 이는 다익스트라 알고리즘보다 느리기 때문에, 벨만-포드는 간선이 음수일 수 있을 때 씁니다.
내 그래프가 어딘가로 전송되나요?
아니요. 그래프는 브라우저 안에서 만들어지고 탐색되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동