[Algorithm] 다익스트라 알고리즘

데이크스트라 알고리즘 이란, A와 B 사이의 최단거리를 찾는 알고리즘이다.

1. 준비물

최단거리 테이블 (distances), 우선순위큐 (pq)

2. 동작 설명

A. 초기화

• distances 노드들의 값 INF
• distances[‘시작’] = 0
• pq.push(distances[‘시작’], ‘시작’)

B. while pq != empty:

• 현재노드 = pq.pop()
• distances[현재노드] 가 현재노드 보다 작으면 아래 진행할 필요 없음.
• for 현재노드와 연결된 이웃노드들:
  • ‘현재노드 거리 + 이웃노드 가중치’ 가 distances[이웃노드] 보다 작다면, distances[이웃노드] 업데이트하고 pq에 (‘현재노드 거리 + 이웃노드 가중치’, ‘이웃노드’) 푸시

C. distances 반환

3. 코드

import heapq

# my_graph = {
#     1: {2: 2, 3: 3},
#     2: {3: 4, 4: 5},
#     3: {4: 6},
#     4: {},
#     5: {1:1}
# }

# my_graph[u].append((w, v))
# u -> v 의 가중치가 v
# my_graph = [
#     [],
#     [(2, 2), (3, 3)],
#     [(4, 3), (5, 4)],
#     [(6, 4)],
#     [],
#     [(1, 1)]
# ]

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    pq = []

    distances[start] = 0
    heapq.heappush(pq, [distances[start], start]) # distance 기준 heap

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

        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(pq, [distance, adjacent])
    return distances

print(dijkstra(my_graph, 'A'))

4. 관련 문제

백준 1753