Dijkstra Algorithm (다익스트라 알고리즘)
최단 경로 문제?
•
두 노드를 잇는 가장 짧은 경로를 찾는 것
•
가중치 그래프의 경우, 간선 가중치의 합이 최소가 되도록 하는 경로를 찾는 것
최단 경로 유형
1. 단일 출발 - 단일 도착 최단 경로
•
그래프 내의 특정 노드 A에서 출발하여, 다른 특정 노드 B로 도착하는 가장 짧은 경로를 찾는 것
2. 단일 출발 최단 경로
•
특정 노드 A와, 그래프에 존재하는 모든 노드와의 가장 짧은 경로를 찾는 것
이렇게, A에서 출발하여 모든 노드로 가는 최단 경로를 찾는 것!
→ 다익스트라 알고리즘이 위와 같은 경로를 찾는 것이다.
3. 전체 쌍(all-pair) 최단 경로
•
그래프 내의 모든 노드 쌍에 대한 최단 경로를 찾는 것
다익스트라 알고리즘?
•
모든 노드의 최단 거리를 찾는 방법
첫 노드를 기준으로 연결 되어 있는 노드들을 추가하며, 최단 거리를 갱신하는 방법
→ 다익스트라는 첫 노드로부터 그래프 내 모든 노드의 최단 거리를 찾는 것이며, 보통 우선순위 큐로 구현하기 때문에,
→ 첫 노드가 A라면, A 부터 모든 노드의 최단 거리를 저장할 배열, 우선순위 큐 가 필요하다.
1. 초기화
1.
노드의 개수 만큼 배열을 생성하되, 첫 노드(0번 index)의 값은 0으로, 첫 노드를 제외한 모든 값은 무한대로 초기화 한다.(INF 라고 표현)
2.
우선순위 큐를 생성하고, 첫 노드의 가중치를 0으로 하고 넣어준다.
2. 우선순위 큐에서 값을 추출 후, 인접한 노드들과 거리 계산
1.
우선순위 큐에서 노드를 추출 (큐니까 가중치가 FIFO)
2.
추출된 노드와 연결된 인접 노드와의 거리 + 추출된 노드의 가중치 값
→ 배열에 저장된 해당 노드의 값보다 작으면 배열 업데이트 하고, 그 값을 우선순위 큐에 넣는다.
→ 크거나 같으면 아무런 작업 X
따라서, 한 번 실행 결과 배열과 큐는 다음과 같이 업데이트 된다.
3. 2번의 작업을 우선순위 큐가 빌 때까지 진행
이렇게 해서 우선순위 큐에 아무것도 남지 않으면, 경로 저장 배열이 A에서 모든 노드로 가는 최단 경로 결과 값이 된다.
코드
import Foundation
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": [:]
]
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
}
Swift
복사
다익스트라 알고리즘의 시간 복잡도
간선의 개수를 E라고 했을 때,
1.
노드마다 인접한 간선을 모두 검사하는 과정 = O(E)
2.
우선순위 큐에 insert/pop 하는 과정 = O(logE)
이렇게 걸린다. 따라서 이 둘을 더한
O(ElogE) 가 다익스트라 알고리즘의 시간 복잡도이다.
Tip
1.
Swift에서 크기를 정해주지 않은 배열보다 튜플의 사용이 더 빠르다.
•
배열 - 참조 타입, 튜플 - 값 타입
•
때문에 배열은 메모리의 힙에 저장되고, 튜플은 스택에 저장되게 된다.
•
힙은 할당과 해제 비용이 스택보다 크기 때문에 튜플을 사용하는 것이 더 빠르다.
◦
힙에 할당, 해제 비용이 더 큰 이유는 힙에 데이터를 저장하기 위해선 적절한 크기의 공간을 찾고 삽입해야하며 해제할 땐 또 해당 공간을 찾아 해제 해주어야 한다.
◦
또한 가장 큰 이유로는 여러 개의 쓰레드가 힙에 메모리를 할당할 수 있기 때문에 무결성 보호를 위해 Lock, 동기화 메커니즘 등을 사용해야 한다는 점이다.
