- 현재
- 큐에 있음
- 확정
- 경로
다익스트라 알고리즘
다익스트라 알고리즘은 도시 사이의 도로처럼 간선에 길이가 있을 때, 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾습니다. 시작 노드에서 바깥으로 퍼져 나가며, 아직 끝나지 않은 가장 가까운 노드를 항상 먼저 꺼냅니다. 노드를 클릭해 거기서 시작하고, 원하면 목표를 고른 뒤, 한 단계씩 진행하며 큐, 더 짧은 길이 나타날 때마다 줄어드는 거리, 그리고 최단 경로가 나타나는 모습을 보세요. 재생을 눌러 탐색을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 노드를 클릭하면 시작 노드가 됩니다. 클릭을 목표로 바꾸고 다른 노드를 클릭하면 그 노드까지의 최단 경로를 찾습니다. 각 간선의 숫자는 그 길이이고, 각 노드의 숫자는 지금까지의 최단 거리이며, 그래프 아래의 줄은 가까운 순서로 놓인 큐입니다. 새 그래프는 다른 그래프를 만듭니다. 노드와 간선 수를 고를 수 있습니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.
작동 원리
- 노드를 클릭해 시작 노드로 정합니다. 경로를 찾으려면 클릭을 목표로 바꾸고 다른 노드를 클릭하세요.
- 재생을 누르거나, 단계와 뒤로로 한 단계씩 이동하세요. 단계 슬라이더를 끌면 탐색의 원하는 곳으로 이동합니다.
- 그래프 아래의 큐와 각 노드의 거리를 지켜보세요. 새 그래프로 다른 그래프를 시도할 수 있습니다.
다익스트라 알고리즘의 작동 방식
시작 노드의 거리를 0, 다른 모든 노드를 무한대로 두고, 시작 노드를 큐에 넣습니다. 그리고 반복합니다. 큐에서 거리가 가장 작은 노드를 꺼내 그 거리를 확정으로 표시합니다. 확정되지 않은 이웃 노드마다 그 노드의 거리에 간선 길이를 더합니다. 그 합이 이웃 노드의 지금까지 거리보다 짧으면 새 거리가 되고, 그 노드가 그곳으로 가는 길로 기억되며, 이웃 노드가 큐에 없었다면 큐에 들어갑니다. 큐가 비면 도달할 수 있는 모든 노드의 최단 거리가 정해집니다.
가장 가까운 노드가 확정되는 이유
어떤 노드가 큐에서 가장 가까울 때, 그 노드로 가는 다른 모든 길은 그래프의 끝난 부분에서 큐에 있는 어떤 노드를 거쳐 나가야 합니다. 그 노드는 적어도 그만큼 멀고, 그 뒤에 더하는 간선은 음수일 수 없습니다. 그러니 다른 길이 더 짧을 수 없습니다. 목표가 처음 도달했을 때가 아니라 큐에서 꺼낼 때에야 확실해지는 것도, 다익스트라 알고리즘이 음수 간선에서 실패하는 것도 이 때문입니다. 그럴 때는 벨만-포드 알고리즘이 필요합니다. 모든 간선의 길이가 1이면 다익스트라 알고리즘은 너비 우선 탐색과 똑같이 동작합니다.
자주 묻는 질문
다익스트라 알고리즘이란 무엇인가요?
간선의 길이가 0 이상인 그래프에서 한 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 방법입니다. 아직 끝나지 않은 가장 가까운 노드를 반복해서 꺼내 그 거리를 확정하고, 그 간선을 이용해 이웃 노드의 거리를 줄입니다.
다익스트라 알고리즘은 왜 음수 간선에서 동작하지 않나요?
노드가 큐에서 가장 가까워지는 순간 그 거리를 확정하기 때문입니다. 나중에 발견된 음수 간선이 더 짧은 길로 그 노드에 돌아올 수 있으므로, 확정된 거리가 틀릴 수 있습니다. 벨만-포드 알고리즘은 합이 음수인 사이클이 없는 한 음수 간선을 처리합니다.
다익스트라와 BFS의 차이는 무엇인가요?
너비 우선 탐색은 간선 수를 세고 일반 큐를 사용합니다. 다익스트라 알고리즘은 간선 길이를 더하고, 항상 가장 가까운 노드를 내주는 우선순위 큐를 사용합니다. 모든 간선의 길이가 1이면 둘 다 같은 거리를 찾습니다.
다익스트라 알고리즘은 얼마나 빠른가요?
우선순위 큐로 이진 힙을 쓰면, 노드 V개와 간선 E개에 대해 작업량이 (V + E) log V에 비례해 늘어납니다. 피보나치 힙을 쓰면 E + V log V입니다. 이 앱은 큐를 정렬된 목록으로 유지하는데, 보여 주기 쉽고 작은 그래프에는 충분합니다.
내 그래프가 어딘가로 전송되나요?
아니요. 그래프는 브라우저 안에서 만들어지고 탐색되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동