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

🕸️ 다익스트라 알고리즘

그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.

출처: 위키피디아

각 정점을 방문하면서 그 정점에 도달하는 최소값을 갱신해주는 방식이다. 다음 정점을 선택할 때 시작정점으로부터 가장 짧은 거리의 정점을 방문해야 한다.

🔥 Swift 구현

실제 구현은 아래와 같다. 아래의 방법으로 구할 경우 다익스트라의 시간 복잡도는 O(V^2 + E)이다.

struct Edge {
    var d: Int
    var w: Int
}

func dijkstra(graph: [[Edge]], start: Int) -> [Int] {
    var distances = Array(repeating: Int.max, count: graph.count)
    var visited = Array(repeating: false, count: graph.count)
    distances[start] = 0 // 시작 정점의 거리 0
    
    for _ in 0..<graph.count {
        var minDistance = Int.max
        var current = -1
        
        /// 가장 짧은 거리의 다음 정점 찾기
        for vertex in 0..<graph.count {
            if !visited[vertex] && distances[vertex] < minDistance {
                minDistance = distances[vertex]
                current = vertex
            }
        }
        
        if current == -1 { break }
        visited[current] = true
        
        /// 간선 정보를 통해 최단거리 갱신
        for edge in graph[current] {
            distances[edge.d] = min(distances[current] + edge.w, distances[edge.d])
        }
    }
    
    return distances
}

🧭 초기 세팅

아래와 같이 리턴할 거리의 배열을 Int.max로 초기화 해준다. 방문체크를 하기 위한 방문배열도 선언해주고... 시작 정점은 거리 0으로 설정한다.

func dijkstra(graph: [[Edge]], start: Int) -> [Int] {
    var distances = Array(repeating: Int.max, count: graph.count)
    var visited = Array(repeating: false, count: graph.count)
    distances[start] = 0 // 시작 정점의 거리 0
    
    //... 생략
}

🚏 가장 가까운 노드 찾기

물론 이부분을 우선순위 큐로 구현한다면 달라지지만 O(N)으로 단순하게 구한다고 생각하면 아래와 같이 방문하지 않은 정점중에서 가장 가까운 거리의 정점을 찾아준다. 

        var minDistance = Int.max
        var current = -1
        
        /// 가장 짧은 거리의 다음 노드 찾기
        for vertex in 0..<graph.count {
            if !visited[vertex] && distances[vertex] < minDistance {
                minDistance = distances[vertex]
                current = vertex
            }
        }
        
        if current == -1 { break }

♻️ 최단거리 갱신

간선 정보를 통해 최단거리를 갱신해준다. 여기서 d는 destination, w는 weight의 약자를 썼다.

        visited[current] = true
        
        /// 간선 정보를 통해 최단거리 갱신
        for edge in graph[current] {
            distances[edge.d] = min(distances[current] + edge.w, distances[edge.d])
        }

💾 입력과 결과

아래와 같이 간선(Edge)가 입력된다면 다익스트라를 활용하면 O(V^2 + E)로 각 정점까지 최단거리를 구할 수 있다!

출처: 위키피디아

let graph: [[Edge]] = [
    [Edge(d: 1, w: 7), Edge(d: 2, w: 9), Edge(d: 5, w: 14)],                    // Vertex 0
    [Edge(d: 0, w: 7), Edge(d: 2, w: 10), Edge(d: 3, w: 15)],                   // Vertex 1
    [Edge(d: 0, w: 9), Edge(d: 1, w: 10), Edge(d: 3, w: 11), Edge(d: 5, w: 2)], // Vertex 2
    [Edge(d: 1, w: 15), Edge(d: 2, w: 11), Edge(d: 4, w: 6)],                   // Vertex 3
    [Edge(d: 3, w: 6), Edge(d: 5, w: 9)],                                       // Vertex 4
    [Edge(d: 0, w: 14), Edge(d: 2, w: 2), Edge(d: 4, w: 9)]                     // Vertex 5
]

print(dijkstra(graph: graph, start: 0)) // [0, 7, 9, 20, 20, 11]

🔨 우선순위 큐를 사용한 다익스트라의 개선

위에서 구현한 것은 처음 고안된 알고리즘이다. 가장 최단거리의 노드를 찾기위해서 모든 정점을 계속 돌면서 체크하게 되는데 이부분을 우선순위 큐(최소 힙)으로 구현하게 된다면, 아래와 같이 구현할 수 있다. 이렇게 되면 시간복잡도는 O(VlogV + ElogV)로 줄어들게 된다.

func dijkstra(_ graph: [[Edge]], _ start: Int) -> [Int] {
    var distances = [Int](repeating: Int.max, count: graph.count)
    distances[start] = 0
    
    var priorityQueue = MinHeap()
    priorityQueue.push((vertex: start, cost: 0))
    
    while !priorityQueue.isEmpty {
        guard let current = priorityQueue.pop() else { break }

        if current.cost > distances[current.vertex] { continue }

        for edge in graph[current.vertex] {
            let cost = current.cost + edge.w
            if cost < distances[edge.d] {
                distances[edge.d] = cost
                priorityQueue.push((vertex: edge.d, cost: cost))
            }
        }
    }
    
    return distances
}