Swift Dijkstra 알고리즘

Swift Dijkstra 알고리즘

 

다익스트라 알고리즘 : 한 지점에서 각각의 특정 지점까지의 최단 경로 - 그리디에 속함

플로이드 워셜 알고리즘 : 모든 지점에서 다른 모든 지점까지의 최단 경로 - dp에 속함

 

간선의 개수 : E

노드의 개수 : V

 

시간복잡도

O(ElogV)

 

 

다익스트라 알고리즘

그래프

 

 

아래는 다익스트라 알고리즘 손으로 분석

다익스트라 알고리즘 손 분석

 

 

샘플 코드

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

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
}

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" : [:]
]