Processing math: 100%

본문 바로가기

Dial's Algorithm

(1)

120. Dial's Algorithm 다이얼 알고리즘(Dial's Algorithm)은 간선들의 가중치가 크지 않은 그래프에서 최단 경로를 구할 때 사용할 수 있는 알고리즘으로,

$0$ -

$1$ BFS의 발전된 버전이라고 생각할 수도 있다. 각각의 간선의 가중치가

$c$ 이하의 정수일 때 다이얼 알고리즘은

$(c+1)$ 개의 큐를 사용하여 최단 경로를 구한다. 큐 대신 스택, 벡터 등을 사용할 수도 있다.

$c = 1$ 일 경우

$0$ -

$1$ BFS와 매우 유사한 형태가 되며,

$2$ 개의 큐를 하나의 덱으로 바꾸면

$0$ -

$1$ BFS와 같아진다. 다이얼 알고리즘의 작동 방식은 다음과 같다. 1. 시작 정점은

$k$ 로부터 정점

$i$ 까지의 최단 경로를

$d_i$ 라고 한다. 2. 정점

$x$ 에서 정점

티스토리툴바