최단경로 - 다익스트라 알고리즘 구체적인 설명(2) - 우선순위큐 활용

이전의 간단한 다이스트라 알고리즘

https://sonlife97.tistory.com/entry/%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%EC%B2%B4%EC%A0%81%EC%9D%B8-%EC%84%A4%EB%AA%85

최단경로 - 다익스트라 알고리즘 구체적인 설명

 

해당 알고리즘의 시간 복잡도는 O(V^2)이라고 했습니다. 왜냐하면 O(V) 번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문입니다.

 

그래서 기존의 알고리즘으로는 노드의 개수가 10,000개를 넘어가는 문제라면 이 코드로는 문제를 해결하긴 어렵다고 볼 수 있습니다.

 

 

 

개선된 다익스트라 알고리즘

개선된 다이스트라 알고리즘은 경로 문제를 최악의 경우에도 시간 복잡도 O(ElogV)를 보장하여 해결할 수 있습니다.

여기서 V는 노드의 개수이고, E는 간선의 개수를 의미합니다.

 

그래서 힙(Heap) 자료구조를 사용합니다. 힙 자료구조를 이용하게 되면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있습니다.

https://sonlife97.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99Heap

자료구조 - 힙(Heap)

 

힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나입니다.

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징입니다.

 

이러한 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다.

파이썬에서는 우선순위 큐가 필요할 때 PriorityQueue, heapq를 사용할 수 있는데. 이 두 라이브러리는 모두 우선순위 큐를 지원합니다. 다만, heapq가 더 빠르게 작동하므로 해당 문제를 해결하는 데 있어서 heapq 라이브러리를 선택해서 사용하겠습니다.

 

우선순위 값을 표현할 때는 일반적으로 정수형 자료형의 변수가 사용됩니다.

 heapq 모듈을 사용하면 숫자, 객체 또는 다른 데이터 유형을 기반으로 한 우선순위 큐를 만들 수 있습니다. 

기본적으로 heapq.heappush(heap, item) 이 함수는 heap에 item을 추가하는 데 사용됩니다. item은 보통 튜플 형태로 (우선순위, 값)으로 표현됩니다. 예를 들어, (3, 'apple')은 우선순위가 3인 apple 값을 나타냅니다.

import heapq

# 빈 리스트를 생성하여 최소 힙으로 사용
heap = []

# 우선순위 큐에 요소 추가
heapq.heappush(heap, (3, 'apple'))
heapq.heappush(heap, (1, 'banana'))
heapq.heappush(heap, (2, 'cherry'))
heapq.heappush(heap, (5, 'date'))

# 우선순위가 가장 높은 요소 추출
highest_priority_item = heapq.heappop(heap)
print(highest_priority_item)  # 출력: (1, 'banana')

이 예제에서는 튜플을 사용하여 각 요소의 우선순위와 값을 함께 저장하고, heappush를 통해 요소를 추가하고 heappop을 사용하여 최소 우선순위 요소를 추출했습니다. heapq 모듈을 사용하면 우선순위 큐를 간단하게 구현하고 관리할 수 있습니다.

 

또한 최소 힙을 최대 힙처럼 사용하기 위해서 일부러 우선순위에 해당하는 값에 음수 부호( - )를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호( - )를 붙여서 원래의 값으로 돌리는 방식을 사용할 수도 있습니다.

 

앞서 우선순위 큐를 구현할 때는 힙 자료구조를 이용한다고 했는데, 사실 우선순위 큐를 구현하는 방법은 다양합니다. 단순히 리스트를 이용해서 구현할 수도 있습니다.

연산	리스트 (List)	힙 (Heap)
삽입 (Insert)	O(1) - 끝에 추가	O(log n) - 요소 삽입 후 힙 재구성
삭제 (Delete)	O(n) - 요소 검색 후 삭제	O(log n) - 최소/최대값 추출 후 힙 재구성

 

이 표는 일반적으로 최소 힙(Min Heap)을 기준으로 작성되었습니다. 최대 힙(Max Heap)의 경우에도 원리는 동일하며, 삭제 작업에 대한 시간 복잡도만 다릅니다.

 

여기서 'n'은 리스트 또는 힙에 저장된 요소의 수를 나타냅니다. 리스트에서 요소를 삭제하려면 요소를 찾기 위해 O(n) 시간이 소요되며, 힙에서는 O(log n) 시간이 소요됩니다. 그러나 힙에서 요소를 추가할 때 O(log n) 시간이 들지만, 리스트에서는 단순히 끝에 요소를 추가하므로 O(1) 시간이 소요됩니다.

따라서 요소의 추가 및 삭제 작업에 대한 시간 복잡도에서 힙은 리스트에 비해 효율적입니다. 특히 큰 데이터 세트에서 우선순위 큐나 정렬 작업을 수행할 때 힙을 사용하면 효율적인 결과를 얻을 수 있습니다.

 

힙을 이용하는 경우 모든 원소를 저장한 뒤에 우선순위에 맞게 빠르게 뽑아낼 수 있으므로 힙은 '우선순위 큐'를 구현하는데 가장 많이 사용됩니다.

 

그래서 우리는 최소 힙을 다익스트라 최단 경로 알고리즘에 적용할 것입니다. 단순히 우선순위 큐를 이용해서 시작 노드로부터 '거리'가 짧은 노드 순서대로 큐에서 나올 수 있도록 다익스트라 알고리즘을 작성하면 됩니다.

 

 

 

개선된 다익스트라 알고리즘 소스코드

import heapq

def dijkstra(graph, start):
    # 시작 노드로부터의 거리를 저장하는 딕셔너리
    distances = {node: float('inf') for node in graph}
    distances[start] = 0  # 시작 노드의 거리는 0으로 초기화
    priority_queue = [(0, start)]  # 우선순위 큐 초기화

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # 현재 노드까지의 거리가 이미 저장된 거리보다 크다면 무시
        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # 더 짧은 거리를 발견한 경우, 업데이트하고 큐에 추가
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 그래프 예시
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start_node = 'A'
shortest_distances = dijkstra(graph, start_node)
print(shortest_distances)