[1]
BFS(너비우선탐색) 알고리즘은 보통의 경우 tree나 graph의 노드들을 탐색하기 위해
queue 자료구조를 이용해 아래와 같은 순서로 동작한다.
1. queue가 비어있는지 확인한다. 비어있으면 종료한다.
2. 비어있지 않다면 queue의 head를 pop해 현재 노드로 접근한다.
3. 현재 노드에서 이동가능한 노드들 중 아직 방문하지 않은 노드를 queue에 push한다.
4. 1번으로 돌아간다.
[2]
하지만 여기서 queue에 push하는 조건을 아래와 같이 바꾸면 최단 거리를 구하는데 사용할 수 있다.
현재 노드에서 방문 가능한 노드 중 아직 방문하지 않은 노드
=> 현재 노드에서 방문 가능하고 (기존에 계산한 출발지에서 다음 노드까지의 거리)보다 (출발지에서 현재 노드까지의 거리 + 현재 노드에서 다음 노드까지의 거리)가 더 짧은 경우
위와 같은 방법을 사용하면 처음 queue에 넣은 노드로부터 접근 가능한 모든 노드들까지의 거리를 계산할 수 있게 된다.
하지만 위와 같은 방법을 사용하기 위해서는 기존의 방법에 비해 추가로 데이터가 필요하다.
출발지 노드로부터 다른 각 노드들까지의 거리를 저장하는 데이터가 필요하다.
초기에는 자기 자신까지의 거리는 0이며 다른 노드들까지의 거리는 무한대이지만 bfsf를 수행하면서 다른 노드들까지의 거리를 계속해서 업데이트 해주어야 한다. 그리고 더 이상 각각의 다른 노드들까지의 거리가 업데이트 되지 않는 시점에 알고리즘은 종료하게 될 것이다.
1. queue가 비어있는지 확인한다. 비어있으면 종료한다.
2. 비어있지 않다면 queue의 head를 pop해 현재 노드로 접근한다.
3. 현재 노드에서 이동가능한 노드들 중 (기존에 계산한 출발지에서 다음 노드까지의 거리)보다 (출발지에서 현재 노드까지의 거리 + 현재 노드에서 다음 노드까지의 거리)가 더 짧은 경우 해당 다음 노드를 queue에 push한다.
4. 다음 노드까지의 거리를 업데이트한다.
5. 1번으로 돌아간다.
[3]
여기서 위의 최단거리 계산 방법을 응용하면 또 다른 최단거리를 계산할 수 있다.
위의 조건을 아래와 같이 조금 수정해
(기존에 계산된 현재 노드에 접근이 가능한 다른 노드들부터 목적지까지의 거리) > (현재 노드부터 목적지까지의 거리 + 현재 노드에 접근이 가능한 노드부터 현재 노드까지의 거리)
인 경우에 queue에 넣도록한다면
위에서의 최단 거리가 처음 시작하는 노드로부터 다른 노드들까지의 거리를 계산한 것이라면
자기 자신을 제외한 다른 모든 노드들로부터 자기 자신까지의 거리를 계산하는 알고리즘이 된다.