알고리즘/최단경로
[최단경로] 02. 다익스트라
- -
이번 포스트에서는 발음이 정말 생소한 다익스트라 알고리즘에 대해서 살펴보자. 이 알고리즘은 에츠허르 다익스트라라는 네델란드 개발자분이 고안한 알고리즘이라고 한다. 튜링상을 받은 어마어마한 분이다.!
다익스트라 알고리즘이란?
다익스트라 알고리즘은 특정 시작 정점에서 거리가 최소인 정점을 계속해서 선택해 나가다보면 결국 각 정점까지의 최단거리를 구할 수 있다는 생각에서 출발한 알고리즘이다.
다익스트라 알고리즘은 현재 상태에서 가장 최선이라고 생각되는 정점들을 쭉~탐색해 나가는 그리디 알고리즘이다. 검증이야 이미 다익스트라 아저씨가 잘 해놓은 상태이다. ㅎ
아래와 같은 그래프를 생각해보자. 출발점 S에서 목적지 D로 가는 경로는 총 3가지가 가능하다.
S->D로 한방에 갈 수도 있지만(W_SD = 50) 이 길은 시골길이어서 엄청 오래걸린다고 생각해보자. S에서 V1을 거쳐 D로 가는 길은 고속화 도로가 설치되어 경유지가 있음에도 불구하고 더 빠를 수 있다 (W_SV1 + W_V1D = 30 < W_SD).
이처럼 가중치가 있는 그래프는 BFS로는 탐색할 수 없다. BFS에서는 S-D가 최단이다.
마찬가지로 S -> V2 -> V1 -> D로도 갈 수 있는데 원래는 W-SV1이 20의 비용으로 최소인줄 알았는데 오히려 V2를 겨쳐가면 즉 W_SV2 + W_V2V1이 15의 비용이므로 결국 S에서 V1에 가능 최소 경로는 S->V2->V1이 최소임이 밝혀진 것이다.
이렇게 S에서 D로 가는 길목에 있는 경유지를 계속 최단으로 갱신(이런 과정을 relax 라고 한다)하다 보면 결국은 최단 경로가 구성되는 성질을 이용하는 알고리즘이 다익스트라 알고리즘이고 MST를 찾는 Prim 알고리즘과 전개 방식이 매우 유사하다.
알고리즘 전개 방식
그럼 다익스트라 알고리즘이 어떻게 전개되는지 살펴보자. 여기서는 비용 뿐 아니라 그 최단 비용을 구성하는 경로까지 살펴보자.
준비물
다익스트라 알고리즘은 특정 출발점에서 다른 모든 정점까지의 최단 거리를 구해가는 알고리즘이다. 이를 위해 출발점에서 정점들까지의 비용을 저장할 테이블(1)이 필요하다. 이 테이블의 모든 항목들은 무한대로 초기화 해둔다.그리고 중복 방문 방지를 위한 테이블(2), 추가로 경로를 저장하고 싶다면 부모 정점을 표현하기 위한 테이블(3)이 필요하다.
아래와 같이 7개의 정점과 유향의 가중치 그래프가 주어졌을 때 다익스트라를 위한 준비물이다.
출발!!
이제 탐색이 시작한다 다익스트라는 특정 정점(출발점)에서 다른 모든 정점까지의 거리를 구하기 때문에 출발점의 비용을 0으로 처리해서 처음에 선택될 수 있게 해줘야 한다.
일단 1번 정점에서 탐색을 시작한다고 하자.
단계 1
이후로는 계속해서 반복되는 과정이다. 비용 테이블에서 가장 비용이 작은 정점(여기서는 1이 0)을 찾아서 방문처리 한다.
단계 2
이제 1번 정점에서 갈 수 있는 다른 정점들을 찾아보자. 2번과 3번 비용은 1번 정점을 경유해서 방문하므로 1번 정점의 누적 비용(0)에 1번 정점에서 해당 정점까지의 비용을 더해서 각각 0+2, 0+1이 된다.
이 값들은 기존의 비용 ∞ 대비 짧아진 비용이기 때문에 테이블의 값을 업데이트 해준다. 그리고 2번 정점과 3번 정점의 부모를 일단 1번 노드로 채워줄 수 있게 되었다.
이제 다시 비용 테이블에서 아직 미방문인 지점 중 최소 비용으로 갈 수 있는 정점(3)을 찾아서 단계 1부터 목적지에 도달할 때까지 위 과정을 계속 반복해주면 된다. 뻔하지만 일단 가보자.
단계 3
이제 미방문인 지점 중에서 비용이 가장 저렴한 정점은 비용 1인 3번이다. 출발점에서 부터 최소의 비용으로 누적해가며 이 지점에 왔기 때문에 이보다 더 저렴하게 3번을 올 수 있는 가능성은 없다. 따라서 3번 정점을 방문처리하고 시작 정점에서 출발하여 이 정점을 통해서 갈 수 있는 정점들에 대한 누적 비용을 업데이트 한다. 즉 4는 1->3까지의 누적 비용 1에 3-> 4의 비용 1을 더해서 2가 되고 5는 1->3까지의 누적 비용 1에 3->5의 비용이 추가되어 3이 된다.
그리고 3번 정점의 부모 정점도 1로 확정되고 4, 5번 노드의 부모 후보들은 3이 된다. 하지만 확정은 아니다. 방문 처리될 때가 확정이다.
단계 4
다음 미방문이면서 최소 비용 정점은 2번 또는 4번이다. 누구를 선택해도 상관은 없는데 여기서는 2번을 선택한 상태로 진행해본다.
2에서 갈 수 있는 정점은 6번 정점 하나 뿐이고 3의 비용으로 도달할 수 있다. 따라서 6번 정점까지의 누적 비용은 1->2의 비용 2에 2->6의 비용 3을 더해서 5가 된다.
테이블에 비용과 방문 여부를 업데이트 하고 부모도 1로 확정한다. 6의 부모 후보로는 일단 2번이 가능해졌다. 하지만 확정은 아니다.
단계 5
다음 미방문이면서 최소 비용 정점은 4번이고 4번을 통해서 갈수 있는 정점은 6번이다.
6번은 이전 탐색에서 비용이 5였는데 4번 정점을 통해서 탐색해보니 1->4의 누적 비용 2에 4->6의 비용 2를 더하면 4이다. 따라서 기존의 경로보다 4번을 통한 탐색이 더 짧음을 알 수 있다.!
따라서 단계 4에서 업데이트 했던 비용을 4로 바꾸고 부모의 후보도 2에서 4로 변경된다. 물론 4번 정점은 방문 처리하고 부모도 3으로 확정된다.
단계 6
다음 미방문에 최소 비용 정점은 5번이다. 이 정점을 확정하고 다음 정점을 찾아보면 6번이 대상이다.
하지만 5를 거쳐 6으로 가는 경로는 1->5의 비용 3에 5->6의 비용 3을 더해서 총 6으로 기존 비용 4보다 더 비싸다!. 당연히 그 길은 선택되지 않을꺼니까 비용은 업데이트 되지 않고 5번 정점에 대한 방문여부와 부모만 확정된다.
단계 7
헉헉헉.. 거의 다 왔다. 애초에 그래프를 좀 더 작게 그릴껄 후회된다. ㅜㅜ
다음의 미방문이면서 최소 비용 정점은 6이고 여기서 방문할 수 있는 정점은 7이다.
7로 가는 비용은 1->6의 누적 비용 4에 6->7의 비용 1을 더해 5가 된다. 또한 6번 정점의 방문여부가 업데이트 되고 부모가 확정된다.
단계 8
드디어 마지막 단계이다. 마지막 미방문 최소 비용 정점은 7번이고 더 이상 탐색할 수 있는 경로는 존재하지 않는다.
따라서 7 번 정점에 대한 방문 여부가 업데이트 되고 부모가 6으로 확정되었다.
결과 활용하기
| 정점 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 비용 | 0 | 2 | 1 | 2 | 3 | 4 | 5 |
| 방문 | T | T | T | F | T | T | T |
| 부모 | 1 | 1 | 3 | 3 | 4 | 6 |
최종적으로 작성된 테이블을 살펴보면 비용은 출발점 1번에서 부터 각각의 정점까지 이르는 최소 비용이 된다.
그리고 경로는 정점의 부모를 역순으로 추적해주면 된다. 예를 들어 7번 정점은 7 <--6 <-- 4 <-- 3 <--1의 경로를 통해서 방문하면 가장 저렴한 5의 비용으로 방문이 가능하다.
음의 가중치는 안돼요!!
타임머신이 설치되었다면..
다익스트라 알고리즘은 음의 가중치가 있는 간선에서는 사용할 수 없다고 했는데 이유를 살펴보자. 만약 2번 정점에서 3번 정점으로 가는 길에 타임머신을 설치해서 오히려 시간이 줄어들 수 있는 경우를 생각해보자.
아래 그래프에서 보듯이 이미 3번 정점은 출발점 1에서 가장 저렴한 비용으로 탐색할 수 있는 정점이므로 방문 처리가 완료된 상황이다.
이 상태에서 다음 최소 비용 정점 2를 탐색하고 여기서 다음 정점을 살펴보는데 3번 정점을 갈 때 오히려 비용이 2+(-5)가 되어서 기존 비용보다 더 저렴해져버린다. 그럼 앞서 선택한 3번 정점이 최선의 선택이 아닌게 되고 전체적인 알고리즘이 망가질 수밖에 없다. 그리디는 한번 결정된 최선을 다시 변경하지 않는다.
따라서 다익스트라 알고리즘은 음의 가중치 그래프에서는 동작할 수 없다.
알고리즘 구현 1
배열을 이용한 비용 관리
그럼 위 과정을 코드로 살펴보자.
static void dijkstra(int start) {
// 1. 준비물
int[] accumCost = new int[V+1];// 모든 정점까지의 누적 비용을 관리할 배열
boolean[] visited = new boolean[V+1];// 방문 여부를 관리할 배열
int[] parent = new int[V+1];// 부모 정점에 대한 정보
// 2. 초기화: 일단 출발점을 제외하고는 모두 탐색할 계획
Arrays.fill(accumCost, INF);
accumCost[start] = 0;
// 3. 모든 정점들의 개수만큼 반복
for (int v = 1; v <= V; v++) {
// 3-1. 아직 미방문인 지점 대상으로 출발점에서의 누적 비용이 최소 비용인 정점 찾기
int minVer = 0, minCost = INF;
for (int i = 1; i <= V; i++) {
if (!visited[i] && accumCost[i] < minCost) {
minCost = accumCost[i];
minVer = i;
}
}
// 3-2. 이제 최소 정점은 최단 거리가 확실!! --> 방문 처리
visited[minVer] = true;
// 3-3. 연결 가능한 지점들 찾아가기 --> 업데이트
for (LinkNode next = graph[minVer]; next != null; next = next.link) {
// 아직 미방문이고 현재 dist에 등록된 거리가 minVer를 거쳐서 온 거리보다 길다면 업데이트
if (!visited[next.i] && accumCost[next.i] > accumCost[minVer] + next.cost) {
accumCost[next.i] = accumCost[minVer] + next.cost;
parent[next.i] = minVer;
// 여기서 방문체크 하지 않고...
}
}
} // for
// 4. 결과 확인 및 활용
System.out.println(Arrays.toString(accumCost));
System.out.println(Arrays.toString(parent));
for(int i=1; i<accumCost.length; i++) {
System.out.printf("%d->%d의 최소비용 %d, 경로: %s%n",start, i, accumCost[i], getPath(i, parent));
}
}
static String getPath(int last, int [] parent) {
StringBuilder path = new StringBuilder();
while(true) {
path.insert(0, last);
int pre = parent[last];
if(pre==0) {
break;
}else {
path.insert(0, "->");
}
last = pre;
}
return path.toString();
}[2147483647, 0, 2, 1, 2, 3, 4, 5]
[0, 0, 1, 1, 3, 3, 4, 6]
1 -> 1의 최소 비용 0, 이동 경로: 1
1 -> 2의 최소 비용 2, 이동 경로: 1->2
1 -> 3의 최소 비용 1, 이동 경로: 1->3
1 -> 4의 최소 비용 2, 이동 경로: 1->3->4
1 -> 5의 최소 비용 3, 이동 경로: 1->3->5
1 -> 6의 최소 비용 4, 이동 경로: 1->3->4->6
1 -> 7의 최소 비용 5, 이동 경로: 1->3->4->6->7
시간을 얼마나 잡아먹었을까요?
이 경우 시간 복잡도는 전체 노드를 대상으로 최소 누적 비용의 정점을 찾아가는 비용이 O(V^2)에 전체 정점에서 각 정점에 연결된 간선을 둘러보는 비용 O(E)를 더해서 O(V^2 + E)라고 할 수 있다. 여기서 E는 V^2에 비해 상대적으로 미미하므로 O(V^2)이라고 간주한다.
알고리즘 구현 2
우선순위 큐의 활용
위 코드는 설명한 알고리즘을 그대로 구현하기 위해서 작성한 코드이다. 매 탐색마다 최소 비용정점을 찾기 위해 O(V^2)의 비용을 사용하고 있는데 이 과정을 최소 비용을 가져다주는 전문가인 PriorityQueue를 사용한다면 비용을 줄일 수 있다.
static void dijkstraPQ(int start) {
// 1. 준비물 -방문처리 필요가 없다.
int[] parent = new int[V+1];// 부모 정점에 대한 정보
int[] accumCost = new int[V+1];
PriorityQueue<LinkNode> pq = new PriorityQueue<>();
// 2. 초기화
Arrays.fill(accumCost, INF);
accumCost[start] = 0;
pq.add(new LinkNode(start, 0, null));
// 3. pq의 내용을 기반으로 탐
while (!pq.isEmpty()) {
// 3-1. 최소 비용 노드 가져오기 - 배열을 반복돌 필요가 없음
LinkNode head = pq.poll();
// 3-2. 연결 가능한 지점들 찾아가기
for (LinkNode next = graph[head.i]; next != null; next = next.link) {
// 현재 dist에 등록된 거리가 minVer를 거쳐서 온 거리보다 길다면 업데이트
if (accumCost[next.i] > accumCost[head.i] + next.cost) {
accumCost[next.i] = accumCost[head.i] + next.cost;
parent[next.i]=head.i;
pq.add(new LinkNode(next.i, accumCost[next.i]));
}
}
} // 탐색 종료
// 4. 결과 확인 및 활용
System.out.println(Arrays.toString(accumCost));
System.out.println(Arrays.toString(parent));
for(int i=1; i<accumCost.length; i++) {
System.out.printf("%d->%d의 비용 %d, 경로: %s%n",start, i, accumCost[i], getPath(i, parent));
}
}배열 버전에 비해서 코드가 줄어들었는데 큰 차이 중 하나는 boolean [] visited를 활용한 방문체크가 필요 없어졌다는 점이다. 방문체크가 필요 없는 이유는 P.Q에서는 항상 현재 알려진 최단 거리가 가장 짧은 노드를 꺼내는데 어떤 노드에 대해서 최단 거리가 처음 결정되면 그 이후는 동일 노드가 다시 나오더라도 처음 거리보다는 길기 때문에 자연스럽게 무시되기 때문이다.
그러나 방문체크를 하면 코드는 조금 손이 가지만 불필요한 P.Q 연산을 줄일 수 있어서 실행 시간이 개선될 수 있는 여지가 있다.
[2147483647, 0, 2, 1, 2, 3, 4, 5]
[0, 0, 1, 1, 3, 3, 4, 6]
1 -> 1의 최소 비용 0, 이동 경로: 1
1 -> 2의 최소 비용 2, 이동 경로: 1->2
1 -> 3의 최소 비용 1, 이동 경로: 1->3
1 -> 4의 최소 비용 2, 이동 경로: 1->3->4
1 -> 5의 최소 비용 3, 이동 경로: 1->3->5
1 -> 6의 최소 비용 4, 이동 경로: 1->3->4->6
1 -> 7의 최소 비용 5, 이동 경로: 1->3->4->6->7
시간을 얼마나 잡아먹었을까요?
이 경우 시간 복잡도는 좀 더 복잡한데 일단 전체 정점에서 각 정점에 연결된 간선을 둘러보는 비용 O(E)이 발생하는 것은 동일하다. 문제는 P.Q에 얼마나 많은 원소들이 들아갈 것인가에 따라 달라진다. 만약 그냥 BFS라면 P.Q에 V개의 정점이 들어가겠지만 여기서는 비용을 업데이트 하면서 기존에 정점이 들어있었는지를 고려하지 않고 막 집어 넣기 때문에 좀 더 많은 정점들이 들어간다. 최악의 경우는 매번 정점을 탐색할 때마다 모든 다른 정점으로의 비용이 갱신되는 경우로 이 경우는 최대 O(E)까지 늘어난다. 이 경우 P.Q의 시간 복잡도는 O(logE)니까 전체적으로 O(ElogE)가 된다.
따라서 이 둘을 더하면 O(ElogE + E), 결과로 대충 O(ELogE)가 된다.
일반적으로 우리는 간선보다는 정점의 개수와 연관된 시간복잡도를 선호한다. 간선의 개수 E는 완전그래프를 생각해도 V^2보다 작기 때문에 O(LogE)는 O(logV^2)로 표현할 수 있다.
따라서 최종적으로 P.Q 버전의 시간복잡도는 일반적으로 O(ElogV^2)에서 지수를 상수로 정리하고 날려버리면 O(ELogV)라고 말하는 편이다.
'알고리즘 > 최단경로' 카테고리의 다른 글
| [최단경로] 04. 플로이드 워셜 (1) | 2024.11.21 |
|---|---|
| [최단경로] 03. 벨만포드 알고리즘 (0) | 2024.11.20 |
| [최단경로] 01.최단경로를 위한 알고리즘 소개 (1) | 2024.11.18 |
Contents
소중한 공감 감사합니다