0-1 BFS (1) 썸네일형 리스트형 119. 0-1 BFS $0$-$1$ BFS는 모든 간선의 가중치가 $0$ 또는 $1$인 그래프에서 사용할 수 있는 최단 경로 알고리즘으로, 한 정점에서 다른 정점들까지의 최단 경로를 구한다. 작동 방식은 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다. 3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다. 4. 빈 덱에 정점 $k$를 추가한다. 5. 덱의 맨 앞에서 정점 하나를 뺀다. 이 정점을 $u$라고 하자. 6. $u$가 아직 선택되지 않았으면, $u$를 선택하고 $u$와 인접한 정점을 확인한다. $u$와 인접한 각각의 정.. 이전 1 다음
