Swift) 최단 경로 :: 다익스트라(Dijkstra) 구현 해보기

 

 

 

안녕하세요:) 소들입니다!

이번 포스팅은 최단 경로 알고리즘 중 하나인,

다익스트라에 대해 공부해볼 거예요!!!!! 조금 어려울 수 있지만!!!!

내가보기엔 이론보다 이름이 젤 어려운듯;

 

먼저, 최단 경로의 종류에 대해 알아보고, 다익스트라 알고리즘에 대해 알아볼 것입니다 :)

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 최단 경로 문제란?

 

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

가중치 그래프의 경우, 간선 가중치의 합이 최소가 되도록 하는 경로를 찾는 것

 

말 그대로 우리가 앞서 배웠던 그래프에서 두 노드 간의 가장 짧은 거리를 찾는 것임

근데 보통 최단 경로를 찾는 문제는 다음과 같이 세 가지 유형으로 나뉘는데,

 

 

 

1-1. 단일 출발 - 단일 도착 최단 경로

 

그래프 내의 특정 노드 A에서 출발하여,

다른 특정 노드 B로 도착하는 가장 짧은 경로를 찾는 것

 

자, 만약 다음과 같은 그래프가 있을 때

 

 

 

 

위처럼 특정 노드(A)에서 특정 노드(B)로가는 최단 경로를 찾는 것이

단일 출발 - 단일 도착 최단 경로임!

 

 

 

1-2. 단일 출발 최단 경로

 

특정 노드 A와, 그래프에 존재하는 모든 노드와의 가장 짧은 경로를 찾는 것

 

이게 무슨 말이냐면, 만약 다음과 같이 A, B, C, D, E, F란 노드를 가진 그래프가 있고,

A에 대한 단일 출발 최단 경로를 구한단 것은,

 

 

 

 

이렇게, A에서 출발하여 모든 노드로 가는 최단 경로를 찾는 것이

단일 출발 최단 경로임!! 우리가 배울 다익스트라 알고리즘이 위와 같은 경로를 찾는 것 :)

 

 

 

1-3. 전체 쌍(all-pair) 최단 경로

 

그래프 내의 모든 노드 쌍에 대한 최단 경로를 찾는 것

 

 

 

 

요런 느낌...! (귀찮아서 그래프 매우 단순화해서 표현함ㅎ)

 

 

.

.

.

근데 다익스트라 알고리즘은 2번 방법인,

단일 출발 최단 경로를 구현하는 알고리즘임 :)

 

 

 

 

2. 다익스트라 알고리즘이란?

 

첫 노드를 기준으로 연결 되어 있는 노드들을 추가하며,

최단 거리를 갱신하는 방법

 

오호.........

이건 이론으로 보면 뭔 소리인지 1도 이해 안 가니까,

다익스트라 알고리즘의 과정을 그림으로 설명할 것임!!! :)

 

근데 그전에 먼저,

다익스트라는 첫 노드로부터 그래프 내 모든 노드의 최단 거리를 찾는 것이며!

보통 우선순위 큐로 구현하기 때문에!!!

 

첫 노드가 A라면, A부터 모든 노드의 최단 거리를 저장할 배열,

우선 순위 큐

 

이 두가지가 필요하단 것만 꼭 기억해두고 가셈 :)

않이.. 우선 순위 큐는 어디다 쓰는데염.. 하겠지만,

다음에 나오니 다익스트라를 구현하기 위한 필수 준비물 두 가지라 생각하셈

 

 

 

 

3. 다익스트라 알고리즘의 로직

 

 

 

 

위와 같은 그래프가 있을 때, 첫 노드 A를 기준으로

모든 노드의 최단 거리를 찾는 방법을 다익스트라 알고리즘으로 보여줄 것임!

 

 

 

3-1. 초기화

 

ⓛ 노드의 갯수만큼 배열을 생성하되, 첫 노드(0번 index)의 값은 0으로,

첫 노드를 제외한 모든 값은 무한대로 초기화 한다(inf라고 표현!)

② 우선 순위 큐를 생성하고, 첫 노드의 가중치를 0으로 하고 넣어준다

 

 

 

 

그림으로 보면 이렇게 되겠군 :)

 

 

 

3-2. 우선 순위 큐에서 값을 추출 후, 인접한 노드들과 거리 계산

 

① 우선 순위 큐에서 노드를 추출(Queue니까 가중치가 FIFO)

 

 

 

 

② 추출된 노드와 연결된 인접 노드와의 거리 + 추출된 노드의 가중치 값을 계산하여,

배열에 저장된 해당 노드의 값보다 작으면 배열을 업데이트 하고, 그 값을 우선 순위 Queue에 넣는다

(크거나 같으면 아무 작업X)

 

 

 

 

따라서, 한 번 실행 결과 배열과 큐는 다음과 같이 업데이트 될 것임 !

 

 

 

 

 

3-3. (3-2)번의 작업을 우선 순위 큐가 빌 때까지 한다

 

반복문으로 우선 순위 Queue가 빌 때까지 반복하면 되는데,

위 예제를 그대로 우선 순위 Queue가 빌 때까지 어떻게 반복하는지 보여주겠음 !!

 

 

 

 

 

 

 

1번째 반복

 

 

 

 

2번째 반복

 

 

 

 

3번째 반복

 

 

 

 

4번째 반복

 

 

 

 

5번째 반복

 

 

 

 

으.. 길고 길었따!!!!!

이렇게 해서 우선 순위 큐에 아무것도 남지 않으면,

경로 저장 배열이 A에서 모든 노드로 가는 최단 경로 결과 값이 되는 것임!!!

 

 

 

 

쨔쟌 :) 잘 따라 왔으면 어렵지 않았을 것.. 흑흑

이제 코드로 구현 해보쟛

 

 

 

 

4. 코드로 구현 해보기

 

4-1. 탐색할 그래프 미리 만들어두기

 

음.. ~ 여기선 데이터를 갖고 그래프를 어떻게 구현하냐!는 다루지 않음

다만, 이미 구현되어 있는 그래프를 어떻게 탐색하는지만 다룰 것임 :)

 

 

let graph: [String: [String: Int]] = [
    "A" : ["B": 9, "C" : 1, "D" : 15],
    "B" : ["E": 10],
    "C" : ["B": 5, "E" : 3],
    "D" : ["E": 10],
    "E" : ["F": 7],
    "F" : [:]
]

 

 

하드코딩 완료......ㅎ

 

 

 

4-2. 우선 순위 큐를 위한 최대 힙 추가하기

 

음....이건 제가 이전 포스팅에서 구현한 것을 그대로 썼음 :)

코드는 아래 깃헙 주소에서 줍줍하실 수 있음!! 난 따로 파일로 추가 했음

 

근데 내가 만든 Heap은 Comparable 프로토콜을 준수하기 때문에,

다음과 같이 Comparable을 준수하는 구조체를 따로 만들어줬음!!

 

 

struct NodePriority: Comparable {
    static func < (lhs: NodePriority, rhs: NodePriority) -> Bool {
        lhs.priority > rhs.priority
    }
    var node: String = ""
    var priority: Int = 0
}

 

 

요롷게 👀

Heap의 값 비교는 구조체의 priority로 하게끔!!!

 

 

 

4-3. 다익스트라 구현하기

 

func dijkstra(graph: [String: [String: Int]], start: String) ->  [String: Int] {
    var distances: [String: Int] = [:]
    var priorityQueue = MaxHeap(NodePriority.init(node: start, priority: 0))
    
    for key in graph.keys {
        let value = key == start ? 0 : 2147483647
        distances.updateValue(value, forKey: key)
    }
    
    while !priorityQueue.isEmpty() {
        guard let popped = priorityQueue.pop() else { break }
        
        if distances[popped.node]! < popped.priority {
            continue
        }
        
        for (node, priority) in graph[popped.node]! {
            let distance = priority + popped.priority
            if distance < distances[node]! {
                distances[node] = distance
                priorityQueue.insert(NodePriority.init(node: node, priority: distance))
            }
        }
    }
    return distances
}

 

 

흠.. Swift의 Int형 Infinity 값을 얻는 방법을 모르겠어서 ㅜㅜ

그냥 Int 자료형의 최대 크기로 해버림 흑흑...

 

코드 구현하기 전 다익스트라 방법에 대해 제대로 이해 했다면,

전~~혀 어렵지 않을 코드라 생각 하지만!! 

만약 제 코드에 틀린 부분이나 피드백할 부분 있으면 꼭 댓글 주세요 :)

 

전체 코드가 필요하다면 요기서 확인해 주셈..!

 

 

 

 

5. 다익스트라 알고리즘의 시간 복잡도

 

마지막! 시간 복잡도를 알아보고 끝내겠음!!

먼저, 다익스트라 알고리즘은 두 과정을 거치는데

간선의 갯수를 E라고 했을 때,

 

① 노드마다 인접한 간선을 모두 검사하는 과정 = 𝑂(𝐸)

② 우선순위 큐에 insert/pop 하는 과정 = 𝑂(𝑙𝑜𝑔𝐸)

 

이렇게 걸림!! 따라서 이 둘을 더한

 

𝑂(𝐸𝑙𝑜𝑔𝐸)

 

가 다익스트라 알고리즘의 시간 복잡도임 :)

 

 

 

 

 

 

 

.

.

.

이거 구현 하는데.. 우선 순위 큐를 Swift에서 어떻게 구현하나 하다가

우선 순위 큐 또한 포스팅 해버렸다....!!!!!!!!!!!!

혹시 이해 안 가거나, 잘못된점 피드백은 언제든 댓글 환영입니다!! 🌸