[4주차] 다익스트라 알고리즘

다익스트라 알고리즘?

가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘

 

다익스트라 알고리즘 (출처 : 위키백과)

 

 

작동 순서

 

위 이미지에서 시작 정점인 a(1번 노드)에서 b(5번 노드) 정점으로 갈 때,

시작 정점	방문 정점 (현재 누적 가중치)
1번 노드	2번 노드 (7)	3번 노드 (7 + 10 = 17)	4번 노드 (7 + 10 + 11 = 28)
			6번 노드 (7 + 10 + 9 = 26)
		4번 노드 (7 + 15 = 22)	5번 노드 (7 + 15 + 6 = 28)
	3번 노드 (9)	4번 노드 (9 + 11 = 20)	5번 노드 (9 + 11 + 6 = 26)
		6번 노드 (9 + 2 = 11)	5번 노드 (9 + 2 + 9 = 20) >> 최단거리
	6번 노드 (14)	5번 노드 (14 + 9 = 23)

 

최단 거리는 1번 노드 > 3번 노드 > 6번 노드 > 5번 노드 경로 임을 알 수 있다.

 

 

Python

작동 순서를 코드로 표현하면 다음과 같다.

import heapq

def dijkstra(start, graph):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    parent = {node: None for node in graph}  # 경로 추적용
    queue = [(0, start)]

    while queue:
        current_dist, current_node = heapq.heappop(queue)

        if current_dist > distances[current_node]:
            continue

        for adjacent, weight in graph[current_node]:
            distance = current_dist + weight
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                parent[adjacent] = current_node  # 어디서 왔는지 기록
                heapq.heappush(queue, (distance, adjacent))

    return distances, parent

def get_path(parent, start, end):
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = parent[current]
    path.reverse()
    return path

# 그래프 (문제와 동일)
graph = {
    1: [(2, 7), (3, 9), (6, 14)],
    2: [(1, 7), (3, 10), (4, 15)],
    3: [(1, 9), (2, 10), (4, 11), (6, 2)],
    4: [(2, 15), (3, 11), (5, 6)],
    5: [(4, 6), (6, 9)],
    6: [(1, 14), (3, 2), (5, 9)]
}

# 실행
start, end = 1, 5
distances, parent = dijkstra(start, graph)
shortest_path = get_path(parent, start, end)

print(f"1번 → 5번 최단 거리: {distances[end]}")
print(f"1번 → 5번 최단 경로: {' -> '.join(map(str, shortest_path))}")

 

실행 결과

1번 → 5번 최단 거리: 20
1번 → 5번 최단 경로: 1 -> 3 -> 6 -> 5