[알고리즘] 최단경로 알고리즘

최단경로 알고리즘

두 노드를 잇는 가장 짧은 경로를 찾는 문제
가중치 그래프에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

종류

1. 단일 출발 및 단일 도착 최단경로 문제 (1:1)
2. 단일 출발 최단경로 문제 (1:N) --> 다익스트라 알고리즘
3. 전체 쌍 최단경로 (M:N)

다익스트라 알고리즘 로직

첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단거리를 갱신하는 기법
첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트

1. 첫 정점을 기준으로 배열을 선언하여, 첫 정점에서 각 정점까지의 거리를 저장
   • 초기의 첫 정점의 거리는 0, 나머지는 무한대(inf)로 저장
   • 우선순위 큐에 (첫 정점, 거리 0) 만 먼저 넣음
2. 우선순위 큐에서 노드를 꺼냄
   • 꺼내진 노드에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 거리를 비교
   • 첫 정점에서 각 노드로 가는 거리가 더 짭을 경우, 배열에 해당 노드의 거리를 업데이트
   • 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣음
     -- 더 긴 거리를 가진 거리의 경우에는 따로 작업을 하지 않음
   • (우선순위 큐에서 꺼낼 노드가 없을 때까지 반복)

코드

(그래프 형태)

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}
}

  import heapq

def dijkstra(graph, start):
    
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        if distances[current_node] < current_distance:
            continue
            
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
                
    return distances

시간 복잡도

O(E logE)