[Algorithms] 우선순위 큐 다익스트라
[Algorithms] 우선순위 큐 다익스트라
안녕하세요? 정리하는 개발자 워니즈입니다. 이번시간에는 최단거리 알고리즘인 다익스트라에 대해서 정리를 해보려고 합니다.
1. 다익스트라 기본 개념
다익스트라 알고리즘은 너비우선탐색(BFS)를 기본으로 합니다. 모든 정점의 거리를 초기에는 무한대로 세팅을 해줍니다.
위의 그림에서 (b)를 보게 되면, 최초 시작 정점인 s로부터 BFS의 알고리즘을 적용하여 2개의 각정점으로 거리를 확인하고 있습니다. s->t로 가는 것은 10으로, s->y로 가는것은 5로 업데이트를 수행합니다. 초기값이 무한대로 세팅이 되어있으므로, 무한대보다 모든값들은 작기 때문에, 초기에 BFS를 수행하게 되면 해당 간선 정보로 업데이트를 하게 됩니다.
(c)를 보게되면, 다음 너비우선탐색에서 정점을 호출하게 되고 다음 깊이인 y에서 연결된 간선정보로 확인을 수행하게 됩니다. y->t로 가는 값은 +3이 더해져서 8이 되었습니다. 기존에 s->t로 가는 간선정보인 10보다 8이 더 최단이기 때문에 업데이트를 수행하게 됩니다. 같은 방식으로 y->x, y->z도 모두 확인을 하고 업데이트를 해줍니다.
(e)를 보게 되면, 정점 t에서 x를 9로 업데이트를 수행하게 됩니다. 그리고 (d)를 보게 되면, 정점 z에서 x로 가는 간선정보인 +6을 더해주게 되어, 13이 되는데 이는 s->y->t->x로 이어지는 9값보다 크게 되어 업데이트를 하지 않습니다. 끝으로 x의 정점을 확인하게 되고 연결되어있는 간선이 없기 때문에 알고리즘을 종료하게 됩니다.
2. 다익스트라의 단점
다익스트라 알고리즘의 최대 단점은 가중치가 음수인 경우 작동하지 않는다는 점입니다.
위의 그림에서 보면, A노드에서 시작합니다. A->C가 간선의 최소이기 때문에 C를 선택하게 됩니다. 그리고 C노드에서 갈수 있는 간선의 방향을 봤더니, C->E가 최소가 되고, 1을 찍고 종료하게 됩니다. 실제로는 A->C>B>E로 가야만, 최단거리가 되겠지만, A->C>E로 간 후 종료를 합니다. 다익스트라 알고리즘은 그리디 알고리즘에 기초를 두고 있습니다. 최소힙에의해서 cost가 가장 최단거리인것만 더해나가기 때문에 위와 같이 음수인 간선에 대해서 처리를 하지 못합니다.
음수인 간선에 대해서는 벨만-포드 알고리즘에 의해서 해결할 수 있습니다. 이부분은 다음번 포스팅에서 정리하도록 하겠습니다.
3. 우선순위 큐
기본적으로 다익스트라를 구현하기 위해서는, 시작점이후의 모든 정점에서 한번씩 거리(간선)을 측정해서 합산하면서 계속해서 업데이트를 해줘야 합니다. 그렇게 되면, E+V^2만큼의 시간 복잡도를 갖고 있습니다. 정점의 갯수가 커지면 커질수록 영향도가 더 커지기 때문에 최종적으로는 V^2의 복잡도를 갖고 있습니다.
이렇게 되면, 알고리즘 문제를 해결할 때, 정점의 갯수에 지대한 영향을 받게 됩니다. 따라서, 이부분에서 최적화를 해야되는데 앞서 정리했던 Priority Queue를 이용하면 복잡도를 줄일 수 있습니다. 바로 MinHeap을 이용하게 되는 것인데, 최단 거리(간선정보)를 갖고 있는 정점을 찾기 위해서 탐색을 수행하는데 여기서 logV만큽의 시간 복잡도를 갖고 있습니다. 그래서 최종적으로는 (E+V) * logV의 시간 복잡도를 갖게 됩니다.
Priority queue를 이용함으로써 시간 복잡도를 현저하게 줄일 수 있습니다. 즉, MinHeap(우선순위 큐)를 이용하여 시간 복잡도를 현저하게 줄 일 수 있게 되었습니다.
위의 그림을 소스의 형태로 나타내 보겠습니다 .
pq = new PriorityQueue();
ad = new ArrayList>();
필자는 2개의 자료구조를 사용했습니다. pqPoint(here와 cost를 변수로 사용)라는 구조체를 만들고, 이부분을 Priority Queue에다가 담습니다. 그렇게 하고 cost에 따라서 최소힙이 구성되도록 하였습니다.
들어오는 정보(노드, 간선)에 대해서는 인접리스트로 구현하였습니다. 리스트 안에 리스트를 담는 형태로 구성했습니다. Point(there, nextDist) 구조체는 다음에 들어갈 노드정보와 거리 정보입니다.
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine().trim());
int from, to, value;
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
value = Integer.parseInt(st.nextToken());
ad.get(from).add(new Point(to, value));
}
위의 코드는 from, to, value형태로 들어오는 정보에 대해서 인접리스트에 담는 코드 입니다. 보시면, from을 기점으로해서 다음 정점의 노드와, 거리 정보를 담습니다.
public static void dijkstra(int src){
pq.add(new pqPoint(src, 0));
dist[src] = 0;
while(!pq.isEmpty()){
pqPoint p= pq.poll();
int cost = p.cost;
int here = p.here;
if(dist[here] < cost) continue;
for (int i = 0; i < ad.get(here).size(); i++) {
int there = ad.get(here).get(i).there;
int nextDist = cost + ad.get(here).get(i).nextDist;
if(dist[there] > nextDist){
dist[there] = nextDist;
pq.add(new pqPoint(there, nextDist));
}
}
}
}
무엇보다 가장 중요한것이, 위의 함수 입니다. 주어진 정보대로 인접리스트에 잘 담았다면, 최단거리를 알아야될 start 노드를 넣고 다익스트라 함수를 수행합니다.
우선순위 큐에다가 최초 src(위의 예에서 1이라고 가정)와 dist정보를 넣습니다. 최초 시작점은 자기 자신이기 때문에 0이 들어갑니다.
우선순위 큐에서 최소힙에 의해 구성된 제일 처음 노드정보를 빼옵니다. 처음시작은 한개밖에 넣지 않았으므로, 위의 예에서는 1이 나올 것입니다.
here = 1, cost = 0 가 나오게되고, dist[1] = INF < 0 에 의해서 넘어갑니다.
for (int i = 0; i < ad.get(here).size(); i++) {
int there = ad.get(here).get(i).there;
int nextDist = cost + ad.get(here).get(i).nextDist;
if(dist[there] > nextDist){
dist[there] = nextDist;
pq.add(new pqPoint(there, nextDist));
}
}
위의 부분이 바로 인접리스트에서 정보를 빼오고, for문을 수행하면서 체크를 합니다. 1정점을 빼오면 다음과 같은 정보가 있습니다
there = 2, cost= 0, nextDist = 2 + 0 , dist[2] = INF > 2 이므로 거리를 업데이트하고, pq에 넣는다.
there = 3, cost= 0, nextDist = 3 + 0, dist[3] = INF > 3 이므로 거리를 업데이트하고, pq에 넣는다.
그럼 다시, while문에 의해서 queue에서 한개를 빼오게 되면,
here = 2, cost = 2가 나오게 됩니다. dist[2] = 2 < 2 에 의해서 넘어갑니다.
인접리스트에서 정보를 뺴오고, for문을 수행하면서 체크합니다.
there = 3, cost = 2, nextDist = 2 + 4, dist[3] = 3 > 6에 의해서 넘어갑니다.
there = 4, cost = 2, nextDist = 2 + 5, dist[4] = INF > 7 이므로 거리를 업데이트하고, pq에 넣는다.
다시, while문에 의해서 queue에서 한개를 빼오게 되면,
here =3, cost = 3가 나오게 됩니다. dist[3] = 3 < 3 에 의해서 넘어갑니다.
인접리스트에서 정보를 빼오고, for문을 수행하면서 체크합니다.
there = 4, cost = 3, nextDist = 3 + 6, dist[4] = 7 > 9 이므로 넘어갑니다.
마지막으로, queue에는 4가 담겨져있지만, 간선정보가 없으므로 바로 빠져나옵니다.
4. 관련 알고리즘 문제
5. 마치며...
이번시간에는 최단 거리 알고리즘인 다익스트라에 대해서 알아보았습니다. 다익스트라는 음의 정보에 대해서는 처리를 못한다는 단점이 있습니다. 이러한 부분에 대해서는 벨만포드 알고리즘으로 해결을 할 수 있습니다. 다음시간에는 벨만포트 알고리즘에 대해서 정리를 해보도록 하겠습니다.
