안녕하세요. 이번 시간에는 단일 출발지에서 최단 경로를 찾는 다익스트라 알고리즘에 대해 알아보겠습니다.
단일 출발지에서 최단 경로가 무슨 소리냐면, 한 버텍스에서 다른 모든 버텍스까지의 최단 경로를 찾는다는 소리입니다.
즉 다익스트라 알고리즘을 사용하여 A로부터 시작하면, B, C, D, E, F 모든 버텍스에 대한 최단 경로를 구할 수 있습니다. 생각만 해도 신나죠? 저만 신나나요? ㅠㅠ
일단 모든 버텍스의 최단 거리값을 Infinity(무한)으로 설정합니다. 그리고 시작점(A) 최단 거리값을 0으로 설정합니다. 이제 A와 연결된 B, C의 거리값을 조정하는데, 시작점 거리값에 아크 값을 더한 것보다 도착점 거리값이 크면 도착점 거리값을 더한 값으로 낮춥니다.
무슨 말인지 글로 보면 헷갈리죠? 시작점 거리값(A, 0)에 아크 값(6)을 더한 것(0+6 = 6)보다 도착점 거리값(B, 무한)이 크면 도착점 거리값을 더한 값(6)으로 바꿉니다. 이제 B는 6이 되는 거죠. C도 0 + 3보다 무한(C값)이 더 크기 때문에 C는 3이 됩니다.
이제 A(0), B(6), C(3), 나머지는 무한인 상황에서 B를 기준으로 반복합니다. A, C, D가 연결되어 있습니다. A에서는 B + 아크(6 + 6)보다 A(0)가 작기 때문에 넘어갑니다. C에서는 B + 아크(6 + 2)보다 C(3)가 작기 때문에 역시 넘어갑니다. D에서는 B + 아크(6 + 5)보다 D(무한)이 크기 때문에 D값을 11로 낮춥니다.
A(0), B(6), C(3), D(11), 나머지는 무한인 상황에서 C를 기준으로 반복합니다. A, B, D, E가 연결되어 있습니다. A에서는 C + 아크(3 + 3)보다 A(0)이 작기 때문에 넘어갑니다. B에서는 C + 아크(3 + 2)보다 B(6)가 크기 때문에 B값을 5로 낮춥니다. D에서는 C + 아크(3 + 3)보다 D(11)이 크기 때문에 D값을 6으로 낮춥니다. E에서는 C + 아크(3 + 4)보다 E(무한)값이 크기 때문에 E의 값을 7로 낮춥니다.
이제 A(0), B(5), C(3), D(6), E(7), F(무한)입니다. 이렇게 남은 D, E, F에서도 반복하면 모든 버텍스의 최단 거리가 나옵니다. 거리가 짧을 때만 값을 낮추고, 크면 넘어가기 때문에 최단 거리를 찾을 수 있는 겁니다.
다익스트라 알고리즘은 기본적으로 동적 프로그래밍도 가능하지만 그리디 알고리즘으로 최적화할 수 있다는 점에서 프림 알고리즘과 상당히 비슷합니다. 사실상 프림 알고리즘을 살짝 변형한 것과 다름없습니다.
코드로 볼까요?지난 시간 그래프 코드 를 재사용합니다.
Graph.prototype.shortest = function(startKey) {
var from = this.first;
while (from) {
if (from.key === startKey) {
break;
}
from = from.next;
}
console.log('시작점은 %s입니다', from.key);
var temp = this.first;
var current;
var arc;
while (temp) { // 모든 버텍스 최단거리를 Infinity로 초기화
temp.distance = Infinity;
temp = temp.next;
}
temp = this.first;
temp.distance = 0;
while (temp) { // 반복문을 돌며 최단 거리를 찾음
current = temp;
temp = temp.next;
arc = current.arc;
while (arc) {
if (arc.destination.distance > current.distance + arc.data) {
arc.destination.distance = current.distance + arc.data;
}
arc = arc.nextArc;
}
}
temp = this.first;
while (temp) {
console.log('%s까지의 최단 거리는 %d입니다', temp.key, temp.distance);
temp = temp.next;
}
};var graph = new Graph();
graph.insertVertex('A');
graph.insertVertex('B');
graph.insertVertex('C');
graph.insertVertex('D');
graph.insertVertex('E');
graph.insertVertex('F');
insertTwoWayArc(graph, 6, 'A', 'B');
insertTwoWayArc(graph, 3, 'A', 'C');
insertTwoWayArc(graph, 2, 'B', 'C');
insertTwoWayArc(graph, 5, 'B', 'D');
insertTwoWayArc(graph, 3, 'C', 'D');
insertTwoWayArc(graph, 4, 'C', 'E');
insertTwoWayArc(graph, 2, 'D', 'E');
insertTwoWayArc(graph, 3, 'D', 'F');
insertTwoWayArc(graph, 5, 'E', 'F');
graph.shortest('A');
// A까지의 최단 거리는 0입니다.
// B까지의 최단 거리는 5입니다.
// C까지의 최단 거리는 3입니다.
// D까지의 최단 거리는 6입니다.
// E까지의 최단 거리는 7입니다.
// F까지의 최단 거리는 9입니다.한 가지 제약점은 모든 아크의 값이 양수여야 한다는 겁니다. 음수일 경우에는 다른 알고리즘(벨만-포드)을 써야 합니다. 다익스트라 알고리즘의 시간 복잡도는 자료구조를 어떤 것을 쓰느냐에 따라 다르지만, 배열에서는 O(V^2), 이진 힙에서는 O(ElgV), 피보나치 힙에서는 O(E+VlgV)가 됩니다. 프림 알고리즘과 똑같습니다.
위의 상황에서는 시작점 하나에 대한 최단 경로만 알려줍니다. 만약 모든 점에서의 최단 경로를 찾고 싶으면 어떻게 해야 할까요? 간단합니다. 모든 점에서 다익스트라 알고리즘을 한 번씩 실행하면 됩니다. 점의 개수가 V이니까 복잡도는 배열에서 O(V^3), 이진 힙에서 O(VElgV), 피보나치 힙에서는 O(VE + V^2lgV)가 됩니다.
다음 시간에는 네트워크 플로우에 대해 알아보겠습니다!
익명
