이번 포스팅에서 다루어볼 알고리즘은 그 유명한 다익스트라(Dijkstra) 최단거리 알고리즘이다. 이 알고리즘을 이용하면 가중치 그래프(Weighted Graph)상에 존재하는 특정한 두 정점 (u,v)의 최단거리를 알 수 있다. 실제로 자동차 네비게이션에도 사용되고 있으며 꼭 알아야하는 알고리즘 중 하나이다.
방식은 너비 우선 탐색(BFS) 방식과 유사하다. 그러나 BFS는 가중치가 각각 다른 간선에 대해서는 최단거리를 찾을 수 없다.
아래의 예시를 보면 그 이유를 알 수 있을 것이다.
위 그래프에서 1에서 출발하여 2에 도착하는 최단거리를 구한다고 생각해보자.
눈으로 보기에는 1->3->2가 8로 바로 알 수 있을 것이다. 그러나 이 것에 대해 너비 우선 탐색을 진행하게된다면 1에서 시작해 인접한 노드에 대한 첫번째 탐색에 바로 2를 찾을 것이고 결과는 10이 나오게 된다. 즉, BFS는 가중치가 있는 그래프를 탐색하기에는 적합하지 않다.
따라서 이를 해결해주는 알고리즘 중 하나로 다익스트라 알고리즘이 있다.
특징
- 가중치 그래프(Weighted Graph)의 한 지점에서 그 외 다른 모든 지점까지의 최단거리를 구할 수 있다.- 그래프의 연결 관계(간선)를 리스트에 저장하는 인접 리스트를 사용한다.
- 가중치 그래프(Weighted Graph)에서 음의 가중치를 가지는 간선이 존재하면 안된다. (아래에 작동방식을 보면 이해할 수 있다.)
절차
1. 초기화
다익스트라 알고리즘을 구현하는데 두개의 배열이 필요하다.
- dist 배열 : 각 정점들까지의 최단거리를 저장하는 배열이다. 시작 정점을 0, 그 외의 정점들을 무한대만큼 큰 값으로 초기화를 해준다.
- visit 배열 : 각 정점들의 방문여부를 체크하는 배열이다. 시작 정점은 방문, 그 외의 정점들은 무방문 상태로 초기화 해준다.
갱신 절차는 아래와 같다.
1. dist배열에 저장된 값 중 가장 작으며 아직 방문되지 않은 정점을 선택
2. 선택한 정점과 연결된 모든 정점들에 대하여 아래와 같은 연산을 수행하여 연결된 정점의 최단거리 갱신 ( Vs = 선택한 정점, Vs = 연결된 정점 )
dist[Vi] = min(dist[Vi], dist[Vs ]+W(Vs ,Vi)) // W(Vs ,Vi) : Vs 와 Vs를 연결하는 간선의 가중치
3. 종료 조건
모든 정점이 방문되었다면 모든 정점에 대해서 최단거리를 구한 것이므로 알고리즘을 종료한다.
작동 방식
위에 소개한 절차에 따라 정점 1을 기준으로 각 정점까지의 최단거리를 구해볼 것이다. 이때 배열의 시작 인덱스를 1로 정의한다.방향 그래프에서 a -> b 인 관계가 있을 때 편의상 정점 a에 대해서 b가 연결되어있다고 표현할 것이다.
절차 1에 따라 시작 정점이 1이므로 dist, visit 배열을 위의 그림과 같이 초기화를 시켜준다.
시작 정점 1에 대해서 절차 2-2를 수행한다. 정점 1에 연결된 정점은 2,3으로 기존 dist 값은 모두 ∞였으나 dist[2] = 7, dist[3] = 2로 갱신된다.
절차 2-1에 따라 방문되지 않은 정점 중 dist값이 가장 작은 정점 3을 선택하여 방문을 체크하고 절차 2-2를 수행한다.
정점 3과 연결된 정점 2,4에 대해서 절차 2-2를 적용한 경우 정점 2에 대해서는 기존 dist[2] = 7이였으나 dist[3]+W(3,2)=3으로 더 작으므로 dist[2]를 3으로 갱신해준다. 또한 정점 4에 대해서는 기존 dist[4] = ∞ 였으나 dist[3]+W(3,4)=5로 더 작으므로 dist[4]를 5으로 갱신해준다.
절차 2-1에 따라 방문되지 않은 정점 중 dist값이 가장 작은 정점 2을 선택하여 방문을 체크하고 절차 2-2를 수행한다.
정점 2과 연결된 정점 5에 대해서 절차 2-2를 적용한 경우 정점 5에 대해서 기존 dist[5] = ∞ 였으나 dist[2]+W(2,5)=5로 더 작으므로 dist[5]를 5으로 갱신해준다.
절차 2-1에 따라 방문되지 않은 정점 중 dist값이 가장 작은 정점을 선택하는데 이번 경우는 dist[4] = dist[5] 이므로 정점 번호가 낮은 4를 선택했다. 이렇게 dist가 동일한 경우 순서는 상관이 없다. 왜냐하면 간선의 가중치가 양수이므로 둘 중 어떠한 정점을 선택해도 선택하지 않은 또 다른 정점의 dist 값을 갱신시키지 못하기 때문이다. (절차 2-2의 조건식을 보면 이해가 될 것이다.) 이제 정점 4과 연결된 정점 2,5에 대해서 절차 2-2를 적용한 경우 정점 2에 대해서 기존 dist[2] = 3이고 dist[4]+W(4,2)=6으로 기존 값이 더 작으므로 갱신하지 않는다. 마찬가지로 정점 5에 대해서 기존 dist[5] = 5이고 dist[4]+W(4,5)=10으로 기존 값이 더 작으므로 갱신하지 않는다.
마지막으로 방문하지 않은 정점 5를 선택하고 방문 체크를 한다. 그러나 정점 5와 연결된 정점이 존재하지 않으므로 절차 2-2를 생략한다.
모든 정점이 방문된 상태이므로 다익스트라 알고리즘을 종료한다. 각 정점별 최단거리가 dist 배열에 담아졌다.
시간 복잡도 분석
이때 N은 정점의 개수, M은 간선의 개수이다.
1. 정렬되지 않은 배열에 저장한 경우 - O(N2)
- 갱신 : O(1)
- 탐색 : O(N)
|
1
2
3
4
5
6
7
8
9
10
11
12
|
Dijkstra(G, w , s){
INITIALIZE-SINGLE-SOURCE(G, s)
S <- ∅
Q <- V[G]
while Q != ∅ // 마지막 정점 제외 총 N-1번 수행 -> O(N)
u <- EXTRACT-MIN(∅) // 각 싸이클마다 가장 작은 dist를 가지는 정점 탐색 -> O(N)
s <- S ∪ {u}
for each vertex v ∈ Adj[u] // 총 싸이클동안 모든 간선을 탐색하므로 총 M번 수행 -> O(M)
RELAX(u, v, w) // 절차 2-2를 뜻하는 동작으로 각 간선마다 수행 -> O(1)
}
|
cs |
2. 우선순위 큐에 저장한 경우 - O(MlogN)
- 갱신 : O(log M)
- 탐색 : O(1)
|
1
2
3
4
5
6
7
8
9
10
11
12
|
Dijkstra(G, w , s){
INITIALIZE-SINGLE-SOURCE(G, s)
S <- ∅
Q <- V[G]
while Q != ∅ // 마지막 정점 제외 총 N-1번 수행 -> O(N)
u <- EXTRACT-MIN(∅) // 각 싸이클마다 가장 작은 dist를 가지는 정점 탐색 -> O(1)
s <- S ∪ {u}
for each vertex v ∈ Adj[u] // 전체 싸이클동안 모든 간선을 탐색하므로 총 M번 수행 -> O(M)
RELAX(u, v, w) // 절차 2-2를 뜻하는 동작으로 각 간선마다 수행 -> O(log M)
}
|
cs |
이렇게 dist를 저장하는 방식에 따라 시간복잡도가 달라지는 것을 확인할 수 있을 것이다. 따라서 그래프의 특성에 맞춰 방법을 선택해야 할 것이다.
아래에는 희소그래프, 밀집그래프의 설명과 함께 그래프 특성에 따른 dist를 저장하는 자료구조를 선택하는 예시이다.
- 희소그래프 : O(M)이 O(N)에 근접하는 그래프
- 밀집그래프 : O(M)이 O(N2)에 근접하는 그래프
댓글