최단거리 문제
그래프 상에서 최단거리를 구하는 방법은 다양하다.
대표적으로, 단순히 모든 edge들을 비교하는 Brute Force가 있을 것이다.
하지만 너무 느리고, 그래프가 큰 경우에는 기하급수적으로 느려진다.
이를 해결하기 위해 여러 알고리즘이 등장했다.
Dijkstra 알고리즘
목적
음이 아닌 edge들로 구성된 graph의 최단거리를 계산한다.
기존의 Brute Force 방식보다 매우 빠른 속도로 계산할 수 있다.
알고리즘 설명
1) 먼저, 초기화를 진행한다. A, B, X array를 만든다. 각각이 의미하는 바는 X는 작업을 진행한 vertex, A는 계산된 최단거리, B는 최단거리 path이다. 초기에 A[s]는 모두 0이다.
X가 V(V는 모든 vertex 집합을 의미한다)가 되기 전까지 진행한다.
2) v는 X에 있고, w는 X에 없는 vertex일때, A[v]+l_vw를 최소화하는 w를 찾는다.
이 말은 X, V-X 집합을 연결하는 최단거리를 찾는다는 의미이다. A[v]는 X에 있는 vertex v의 계산된 최단거리이고, l_vw는 v-w edge의 거리이다. 즉, 모든 계산된 vertex의 최단거리+그 vertex에 연결된 edge를 더한 값들을 비교해 최소가 되는 값을 찾아내는 것이다.
3) 찾아낸다면 w를 X에 넣고, A[w]는 A[v]+l_vw로, B[w]는 v까지의 path에 vw를 연결한 것으로 설정한다.
왜 negative edge는 안되는가?
앞서 음이 아닌 edge로만 구성되어야 한다고 말했다. 그 이유는 다음과 같다.
이처럼 값을 단순히 음이 아니게 만들어서 계산하면 오류가 난다. 이는 단순하게도 최단거리 path는 몇 개의 edge로 구성된지 정해진게 아니기 때문이다. 즉, 기존의 최단거리에 edge 수만큼 음이 아닌 값으로 만들어주는 새로운 값을 더해주기에 실제와는 차이가 난다.
시간 복잡도
단순히 이 방식을 사용할 경우에는 O(VE)의 시간 복잡도를 가진다.
이를 해결하기 위해 heap을 사용한다.
이처럼 각 Key들을 heap에 저장하고 꺼내쓰면 아주 빠르게 사용할 수 있다.
Heap에는 V-X의 원소들을 담고, Key[v]는 가장 작은 score를 의미한다. 만약 최단거리가 없다면 +무한으로 설정한다.
Extract-Min을 반복하며 Dijkstra 알고리즘을 반복한다.
이렇게 새로운 값들을 update하면서 heap을 유지한다.
이 방식을 사용하면 총 시간 복잡도는 O((V+E)log(V))를 가지게 된다.
