[알고리즘] 최단경로 (다익스트라)

최단경로

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

종류)

• 단일 출발 및 단일 도착 (하나의 노드에서 다른 하나의 노드까지의 최단 경로)
• 단일 출발 최단 경로 (특정 노드와 그 나머지 노드들 간의 최단 경로)
• 전체 쌍 최단 경로 (u, v)

이 중에서 두 번째에 속하는 다익스트라 알고리즘을 알아보자.

다익스트라

첫 노드를 기준으로, 연결되어 있는 노드들을 추가해 가며, 최단 거리를 갱신
(BFS와 유사)

알고리즘 구현

: 우선순위 큐(MinHeap)를 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내도록 한다.
이렇게 하면 거리가 긴 경로는 (나중에 꺼내지기 때문에) 계산하지 않아도 된다.

1) 첫 노드를 기준으로 배열을 선언 -> 첫 노드에서 각 노드까지의 거리를 배열에 저장한다.

• 초기에 첫 노드의 거리는 0, 나머지는 무한대인 inf로 저장
• 우선순위 큐에 (거리 0, 첫 노드)만 먼저 넣음

2) 우선순위 큐에서 노드를 꺼낸다. (우선순위 큐에 꺼낼 노드가 없을 때까지 반복)

• 처음에는 첫 노드만 저장되어 있으므로, 첫 노드가 꺼내짐
• 첫 노드에 인접한 노드들 각각에 대해,
  '첫 노드에서 각 노드로 가는 거리'와 '현재 배열에 저장되어 있는 거리'를 비교
  -> 배열에 저장되어 있는 거리보다, 첫 노드에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다.
  -> 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 해당 노드 정보를 넣는다.
  (결과적으로 BFS와 유사하게, 첫 노드에 인접한 노드들을 순차적으로 방문)

*만약, 배열에 기록된 (현재까지 발견된 가장 짧은) 거리보다 더 긴 거리를 가진 경우에는 해당 노드와 인접한 노드 간의 거리 계산을 하지 않는다.

import heapq

def dijkstra(graph, start):
    # 노드 정보를 담을 딕셔너리 (노드번호:거리)
    distances = {node:float('inf')for node in graph}
    # 우선순위 큐 생성
    queue = []
    
    # 초기에 출발노드->자기자신의 거리는 0으로 세팅
    distances[start] = 0
    # 우선순위 큐에 (거리0, 노드번호) 추가
    heapq.heappush(queue, [distances[start], start])
    
    # 우선순위 큐가 빌 때까지 반복
    while queue:
        # 우선순위 큐에서 거리가 가장 짧은 노드정보부터 꺼냄
        cur_distance, cur_node = heapq.heappop(queue)
        # 저장된 거리가 현재 거리보다 짧을 경우 계산 건너뜀
        if distances[cur_node] < cur_distance:
            continue
            
        # 꺼낸 노드와 인접한 노드들 각각에 대해!!
        for adj, weight in graph[cur_node].items():
            # 현재 거리에 인접 노드까지 가는 거리를 더함
            distance = cur_distance + weight
            
            # 새로 계산한 거리가 저장된 거리보다 짧을 때
            if distance < distaces[adj]:
                # 해당 노드의 거리를 업데이트하고,
                distances[adj] = distance
                # 우선순위 큐에 해당 노드 정보 넣기
                heapq.heappush(queue, [distance, adj])
    return distances

시간복잡도

: O(E) + O(ElogE) = O(ElogE)

과정 1) 각 노드마다 인접한 간선들을 모두 검사 => O(E)
과정 2) 우선순위 큐에 노드/거리 정보를 넣고 pop하는 과정 => O(ElogE) *추가 시간은 O(E), 우선순위 큐를 유지하는 시간은 O(logE)

참고) Dave LEE 강의