Processing math: 100%

본문 바로가기

0-1 BFS

(1)

$0$ -

$1$ BFS는 모든 간선의 가중치가

$1$ 인 그래프에서 사용할 수 있는 최단 경로 알고리즘으로, 한 정점에서 다른 정점들까지의 최단 경로를 구한다. 작동 방식은 다음과 같다. 1. 시작 정점은

$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$ 와 인접한 정점을 확인..

티스토리툴바