TIL

🌱 난 오늘 무엇을 공부했을까?

📌 다익스트라 알고리즘

• 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘
• DP를 사용해서 이전 경로를 저장하면서 미래의 경로를 계산한다.

📍 시간 복잡도

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

1. 노드마다 인접한 간선을 모두 검사하는 과정 = 𝑂(𝐸)
2. 우선순위 큐에 insert/pop 하는 과정 = 𝑂(𝑙𝑜𝑔𝐸)

📍 구현

func dijkstra(graph: [String: [String: Int]], start: String) ->  [String: Int] {
    var distances: [String: Int] = [:]
    var queue: [String: Int] = [start : 0]
    
    for key in graph.keys {
        if key == start {
          distances[key] = 0
        } else {
            distances[key] = Int.max
        }
    }
    
    while !queue.isEmpty {
        let element = queue.popFirst()
        
        graph[element!.key]?.forEach {
            let result = element!.value + $0.value < distances[$0.key]! ? element!.value + $0.value : distances[$0.key]
            queue[$0.key] = result
            distances[$0.key] = result
        }
    }
 
    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" : [:]
]

print(dijkstra(graph: graph, start: "A"))

https://babbab2.tistory.com/110