패스
이번 패스에서 바뀜
확인한 간선

  • 현재
  • 거리 있음
  • 사용한 간선
  • 경로
  • 음수 사이클
노드 클릭으로 설정

벨만-포드 알고리즘 더 알아보기

벨만-포드 알고리즘

간선 길이가 음수이면 다익스트라 알고리즘은 망가집니다. 통행료를 받는 대신 돈을 주는 도로 같은 경우죠. 벨만-포드 알고리즘은 그렇지 않습니다. 더 이상 나아지는 것이 없을 때까지 모든 간선을 거듭 확인할 뿐이고, 어떤 사이클 때문에 거리가 끝없이 줄어드는 경우까지 알아챕니다. 노드를 클릭해 거기서 시작하고 패스를 한 단계씩 진행해 보세요. 재생을 눌러 탐색을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 모든 간선은 화살표가 가리키는 쪽으로만 가는 단방향 간선이고, 간선의 숫자는 그 길이이며 음수일 수 있습니다. 노드를 클릭하면 시작 노드가 됩니다. 클릭을 목표로 바꾸고 다른 노드를 클릭하면 마지막에 그 노드까지의 최단 경로를 볼 수 있습니다. 각 노드의 숫자는 지금까지의 거리입니다. 음수 사이클 추가를 체크하면 벨만-포드 알고리즘이 음수 사이클을 찾는 모습을 볼 수 있습니다. 새 그래프는 다른 그래프를 만듭니다. 노드와 간선 수를 고를 수 있습니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.

작동 원리

  1. 노드를 클릭해 시작 노드로 정합니다. 마지막에 경로를 보려면 클릭을 목표로 바꾸고 다른 노드를 클릭하세요.
  2. 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다.
  3. 음수 사이클 추가를 체크하면 벨만-포드 알고리즘이 음수 사이클을 찾는 모습을 볼 수 있습니다. 새 그래프로 다른 그래프를 시도할 수 있습니다.

벨만-포드 알고리즘의 작동 방식

시작 노드에 거리 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를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동