[Python 알고리즘] 다익스트라 구현하기

안녕하세요 여러분~!

이번에는 다익스트라를 배워보도록 하겠습니다.

이름만 들으면 아주아주 어려울 것 같은 요놈

사실 개념만 잘 알아놓으면 보너스 문제라는 사실 알고계셨나요?

다익스트라 자식,, 사실은 외강내유에요😝

 

다익스트라란?

다익스트라는 최단 경로 탐색 알고리즘입니다

최단 경로? 최소값? = Heap?

맞습니다 다익스트라는 힙을 이용하여 구현할 수 있습니다.

 

일단 그림으로 다익스트라 알고리즘의 동작방식을 이해해볼까요?

 

각 노드가 간선으로 연결되어있고 가중치를 가지고 있네요

위에서 말씀드린대로 최단경로탐색을 할건데요

그렇다면 가중치가 작은 경로부터 탐색을 해야겠죠

 

일단 시작노드인 1부터 탐색을 시작해볼까요?

노드1에서 방문 가능한 노드는 2,3,4가 되겠네요

현재 방문할 수 있는 노드의 후보군은 2,3,4 입니다.

이중 가중치가 가장 작은 노드를 방문할건데요

가장적은 비용이 드는 노드2를 방문하겠습니다.

# 현재 후보군 = [2,3,4]
# 누적 가중치와 함께 저장된 힙 요소
# 가중치 기준으로 heappop을 해야되기 때문에 가중치를 앞으로 저장
heap = [(3, 2), (6, 3), (7, 4)]

node = heapq.heappop(heap) # 가중치가 가장 낮은 노드 2 방출

 

노드2를 방문하니 새로 후보군이 생겼네요

노드2와 연결된 노드3을 후보군에 추가합니다

 

 

엇 잠시만요 노드3은 이미 후보군에 있습니다

하지만 노드1에서 추가한 후보군은 비용이 6인 경로였죠?

이번에 추가될 후보군은 비용이 4인 경로입니다.

(1에서 2로 이동할 때 비용 3) + (2에서 3으로 이동할 때 비용 1)

 

비용이 서로 다르기 때문에 후보군에 추가로 넣어줘야 되겠네요!

# 현재 후보군 = [3,4,3]
# 누적 가중치와 함께 저장된 힙 요소
# 가중치 기준으로 heappop을 해야되기 때문에 가중치를 앞으로 저장
heap = [(4, 3), (6, 3), (7, 4)]

node = heapq.heappop(heap) # 가중치가 가장 낮은 노드 3 방출 (비용이 4인 노드3)

 

가중치가 가장 작은 3번노드를 방문합니다.

노드3을 방문했으므로 새로운 후보군 노드4가 추가되고

바로 가중치가 가장 작은 4번노드를 방문합니다.

# 현재 후보군 = [4,3,4]
# 누적 가중치와 함께 저장된 힙 요소
# 가중치 기준으로 heappop을 해야되기 때문에 가중치를 앞으로 저장
heap = [(5, 4), (6, 3), (7, 4)]

node = heapq.heappop(heap) # 가중치가 가장 낮은 노드 4 방출 (비용이 5인 노드4)

 

이제 heap에 남은 요소는 (6,3) 과 (7,4) 입니다.

그러나 안타깝게도 3과 4는 모두 이미 방문한 노드네요

먼저 방문했을 때 가장 적은 비용으로 방문했기 때문에

뒤에 방문하는 경로는 무시하도록 할게요

 

 

이제 다익스트라 템플릿 코드를 살펴볼까요?

import heapq

def dijkstra(graph, start):
    heap = [(0, start)]
    visited = {start: 0}
    
    while heap:
        cur_dir, cur_node = heapq.heappop(heap)
        
        for next_dir, next_node in graph[cur_node]:
            sum_dir = cur_dir + next_dir
            
            if next_node not in visited or sum_dir < visited[next_node]:
                visited[next_node] = sum_dir
                heapq.heappush(heap, (sum_dir, next_node))

 

1. heap에 시작노드를 push합니다.

2. visited를 선언합니다. (리스트 또는 딕셔너리로 선언)

3. heap이 빌 때까지 반복문을 실행합니다.

 

3-1. heap에서 최단 비용 (누적가중치가 가장 작은) 노드를 pop합니다.

3-2. 해당 노드에 첫 방문이거나, 기존 방문보다 비용이 작으면 방문합니다.

3-3. 방문을 해주면서 새로 방문할 수 있는 노드들을 heap에 push 합니다.

 

 

👉 다익스트라 기본문제 풀어보기

[Python] LeetCode - Network Delay Time 문제 풀이

 

 

(문제에 오류가 있거나 이해가 안 가시면 댓글 남겨주세용~😉)