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

안녕하세요 여러분~!

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

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

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

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

 

다익스트라란?

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

최단 경로? 최소값? = 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는 모두 이미 방문한 노드네요

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

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

.

.

.

.

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

func dijkstra(graph: [Int: [(Int, Int)]], start: Int) {
    var heap = Heap()
    heap.push((0, start))
    
    var distances: [Int: Int] = [:]
    distances[start] = 0
    
    while !heap.elements.isEmpty {
        let (cur_cost, cur_idx) = heap.pop()!
        
        guard let childs = graph[cur_idx] else { continue }
        
        for (child_cost, child_idx) in childs {
            var sum_cost = cur_cost + child_cost
            
            if distances[child_idx] == nil || distances[child_idx]! > sum_cost {
                heap.push((sum_cost, child_idx))
                distances[child_idx] = sum_cost
            }
        }
    }
    
    print(distances)
}

 

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

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

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

 

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

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

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

 

 

 

👉 Heap 자료구조에 대한 설명은 아래 포스팅에서 확인해주세요!

[Swift 자료구조] Heap 구현하기

 

 

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

[Swift] Network Delay Time (다익스트라) 문제 풀이

 

 

 

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