다익스트라 - 우선순위 큐

최단 경로 알고리즘

• 두 노드를 잇는 가장 짧은 경로
• 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 경로를 찾는다.

최단 경로 문제 종류

1. 단일 출발 및 단일 도착 - 특정노드에서, 또다른 특정노드의 경로
2. 단일 출발 - 특정 노드에서 해당 노드간 경로를 찾는 문제
3. 전체 쌍 최단 경로 - 그래프 내의 모든 노드 쌍(u,v)에 대한 최단 경로

다익스트라 알고리즘

• 최단 경로 문제 중 2번에 해당
• 하나의 정점에서 다른 모든 정점 간의 각 짧은 거리를 구하는 알고리즘
• BFS와 유사
  • 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든다.
  • 인접 노드 간의 거리부터 먼저 계산하며, 가장 짧은 거리를 배열에 업데이트
  • 여러 로직이 있지만, 가장 개선된 로직은 우선순위 큐 (heapq 라이브러리 사용)

다익스트라 - 우선순위 큐

• MinHeap 방식을 사용하여, 거리가 가장 짧은 노드를 꺼낸다.

)

우선순위 큐에 첫 정점에서 각 정점의 거리를 저장 (첫 정점 : 거리 0)

첫 노드와의 거리를 기반으로 인접노드 거리 계산

우선순위가 가장 높은 노드를 기반(MinHeap)으로 인접노드 거리 계산 (B의 거리가 업데이트)

C다음 우선순위가 높은 D를 기준으로 인접노드 거리 계산 (E, F 거리가 계산된다.)

해당 과정을 반복한다. 우선순위 큐 사용을 통해 불필요한 계산 과정을 줄일 수 있다.

heapq 라이브러리

• 리스트 형태의 경우, 0번 인덱스를 우선순위로 인지

import heapq
queue = []
heapq.heappush(queue, [2, 'A'])
heapq.heappush(queue, [5, 'B'])
heapq.heappush(queue, [1, 'C'])
heapq.heappush(queue, [7, 'D'])
print (queue)
for index in range(len(queue)):
    print (heapq.heappop(queue))

heapq.heappop한 순간 우선순위가 높은 순서대로 pop된다.

heapq.heappush(리스트, [우선순위, 노드])

mygraph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

탐색할 그래프 설정 - dict() 형태

import heapq

def dijkstra(graph, start):

    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start]) # 시작노드를 우선순위 큐에 push

    while queue: # 큐가 빌 동안
        current_distance, current_node = heapq.heappop(queue)

        # 현재 거리보다 이전 거리가 작을경우 pass
        if distances[current_node] < current_distance:
            continue
        # current_node의 value 값들 중 노드의 이름을 adjacent, 거리를 weight
        for adjacent, weight in graph[current_node].items(): 
            distance = current_distance + weight # 현재까지의 거리 + weight

            if distance < distances[adjacent]: # 최단거리를 발견했을 때 
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])

    return distances

시간복잡도

• 과정 1 : 각 노드마다 인접한 간선을 검사
• 과정 2 : 우선순위 큐에 넣고 삭제하는 과정
• 과정별 시간 복잡도
  • 과정 1 : 모든 노드를 방문하므로 O(E) (E는 간선)
  • 과정 2 : 검사할 때마다 배열이 업데이트 되는 경우가 최악
    • 간선 마다 최대 한번 일어나는 시간 O(E)
    • 노드 정보에 대해 우선 순위 큐를 유지하는 시간 O(logE) - root에서 리프노드까지 비교하는 시간
  • O(E) + O(ElogE) = O(ElogE)