[코딩 + 알고리즘 완주반] 21일차. 최단 경로 알고리즘

# 최단 경로 문제

두 노드를 잇는 가장 짧은 경로 찾기

가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로

 

# 단일 출발 및 단일 도착 최단 경로 문제

특정 노드에서 특정 노드에 도착하는 가장 짧은 경로 찾기

 

# 단일 출발 최단 경로 문제

특정노드와 그래프 내 모든 노드 각각의 가장 짧은 경로 찾기

 

# 전체 쌍 최단 경로

그래프 내 모든 노드 쌍에 대한 최단 경로 찾기

 

# 다익스트라 알고리즘 - 너비우선 탐색(BFS)과 유사

하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리 구하기 (단일 출발 최단 경로 문제)

첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를 갱신

 

# 우선순위 큐를 활용한 다익스트라 알고리즘

초기 첫 정점의 거리는 0, 나머지는 무한대로 저장

우선 순위 큐에 첫 정점만 먼저 넣음

우선순위 큐에서 하나씩 꺼내서 첫 정점에서 각 노드로 가는 거리가 현재 배열에 저장되어 있는 거리보다 짧으면 배열 업데이트하고 우선순위 큐에 넣음

우선순위 큐에 꺼낼 노드가 없을 때까지 반복

 

# 알고리즘 구현

heapq 활용하여 우선순위 큐 사용

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

# 시간 복잡도

1. 각 노드마다 인접한 간선들을 모두 검사 O(E)

2.  우선순위 큐에 노드 정보를 넣고 삭제하는 과정 O(ElogE)

총 시간 복잡도 O(E+ElogE) = O(ElogE)