0-1 BFS란 무엇인가.. (feat. BFS, 다익스트라)

bfs와 다익스트라 알고리즘의 차이?

bfs는 가중치가 없는 그래프에서 최단 거리를 구할 수 있는 알고리즘.

다익스트라는  가중치가 있는 그래프에서 최단 거리를 구할 수 있는 알고리즘.

 

다익스트라 알고리즘은 무엇인가?

단계적인 전개 과정은 아래 글을 참고하였다. 

https://techblog-history-younghunjo1.tistory.com/248

[Python] 우선순위 큐를 활용한 개선된 다익스트라(Dijkstra) 알고리즘

 

다익스트라 알고리즘은 어떻게 구현하는가? 

우선순위 큐, 힙(heap): 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나간다.  

힙은 우선순위 큐를 구현하기 위한 자료구조이다. 큰 값이 상위레벨(부모)에 있고, 작은 값이 하위레벨(자식)에 있는 완전 이진 트리의 구조를 가진다. 

파이썬 heapq를 이용하여 구현이 가능하다. 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.  

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함

다익스트라에서 우선순위는 '시작 노드와의 거리가 가장 가까운 노드'를 의미한다. 알고리즘을 반복할 때마다 실시간으로 가장 가까운 노드를 저장한다. 우선순위 큐에는 최단 거리를 기록할 거리 테이블을 정의해 사용한다.

우선순위 큐에서는 최단 거리 노드가 항상 가장 앞에 위치하게 되고, 더 짧은 거리가 등장하면 해당 거리와 노드를 우선순위 큐에 넣어준다. 

import heapq
 
n, m = 6, 11
INF = int(1e9) #무한을 의미하는 값으로 10억
distance = [INF]*(n+1)
start = 1
 
graph = [
    [],
    [(2, 2), (3, 5), (4, 1)],
    [(3, 3), (4, 2)],
    [(2, 3)],
    [(3, 3), (5, 1)],
    [(3, 1), (6, 2)],
    [(3, 5)]
]

def dijkstra(start):
    q=[]
    #시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start]=0
    #q가 비어있지 않다면
    while q:
        print("q:",q)
        print("distance:",distance)
        print("_"*100)
        #가장 최단 거리인 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        #현재 노드가 이미 처리됐다면 skip
        if distance[now] < dist:
            continue
        #현재 노드와 연결된 다른 인접한 노드 확인
        for i in graph[now]:
            cost = dist + i[1]
            #현재 노드를 거치면 이동 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
 
#다익스트라 알고리즘 실행
dijkstra(start)

#모든 노드로 가기 위한 최단 거리 출력
print(distance)

heapq 다익스트라 코드 실행 결과

 

0-1 BFS는 무엇인가?

다익스트라의 시간복잡도 O(ElogV) 대비 O(V+E)의 선형 시간복잡도로 문제를 해결할 수 있는 방법!

단, 가중치가 0, 1만 존재하는 그래프에서 사용한다. 간선의 가중치가 0 또는 1이기 때문에 정점에서 간선(u,v)를 지날 때, 다음과 같은 두 가지 경우 중 한 가지만 발생이 가능하다. 

1. 가중치가 0일 때, v는 u와 같은 레벨이다. (deque 앞부분에 삽입)
2. 가중치가 1일 때, v는 u의 1레벨 아래이다. (deque 뒷부분에 삽입)

 

0-1 BFS는 다음 과정에 따라 최단 경로를 찾게 된다. 

1. deque(덱)의 front에서 현재 노드를 꺼낸다.
2. 연결된 인접 노드를 살펴본다.
3. 현재 노드까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는 데 소비된 비용이면 소비된 비용을 갱신한다.
4. 그 노드가 생신된 상태에서, 만약 그 노드를 향하는 가중치가 0이면 deque의 front, 1이면 덱의 back에 삽입한다.
5. deque에서 더이상 꺼낼 노드가 없을 때까지 위 과정을 반복한다.