Dial's Algorithm (1) 썸네일형 리스트형 120. Dial's Algorithm 다이얼 알고리즘(Dial's Algorithm)은 간선들의 가중치가 크지 않은 그래프에서 최단 경로를 구할 때 사용할 수 있는 알고리즘으로, $0$-$1$ BFS의 발전된 버전이라고 생각할 수도 있다. 각각의 간선의 가중치가 $0$ 이상 $c$ 이하의 정수일 때 다이얼 알고리즘은 $(c+1)$개의 큐를 사용하여 최단 경로를 구한다. 큐 대신 스택, 벡터 등을 사용할 수도 있다. $c = 1$일 경우 $0$-$1$ BFS와 매우 유사한 형태가 되며, $2$개의 큐를 하나의 덱으로 바꾸면 $0$-$1$ BFS와 같아진다. 다이얼 알고리즘의 작동 방식은 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 경로를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치.. 이전 1 다음
