다익스트라 알고리즘 (Dijkstra algorithm)

• 정의 및 설명

 

다익스트라 알고리즘은 주로 도로 교통망 같은 곳에 나타날 수 있는

"그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘"이다. 

 

다익스트라 알고리즘은 매번 주어진 상황에서 가장 좋은 경로를 선택함으로써 만들어가는 탐색 방법인 greedy algorithm(욕심쟁이 알고리즘)의 하나이기도 하다.

 

 

출처 by 위키피디아 

 

위의 그림을 통해 대략적으로 알고리즘을 이해할 수 있다.  

노드 1과 노드 2 사이의 최단 경로를 찾는 알고리즘이라 할 때, 가장 낮은 값을 가진 노드 중 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산 후, 더 작을 경우 인접 거리를 업데이트한다.

위 그림을 보면 다음 방문할 예정의 노드는 회색으로, 이미 방문하여 계산을 완료한 노드는

빨간색으로 표현한 것을 확인할 수 있다.

 

그림에 대해 더 자세히 풀어쓰자면, 시작하는 출발 노드 1 로부터 가장 가까운 정점은 2이므로 2를 방문한다.

2에서 이미 방문한 노드인 1을 제외하고 가장 가까운 정점은 3이므로 3을 방문한다.

이 때, 1->2->3으로 간다면 가중치가 10+7=17 이지만, 1->3으로 간다면 9이므로, 노드 3의 거리를

둘 중에 더 작은 9로 계산한다. (이 비교 과정을 매번 노드에 방문할 때마다 거쳐야 한다.)

이 과정을 반복하여 다음 방문할 노드를 정하고, 모든 노드의 방문이 끝나면

해당 방문 순서가 최단경로가 되고 마지막 노드의 가중치가 총 최단경로의 거리가 되는 것!

 

 

다익스트라 알고리즘에 대한 전체적인 메커니즘을 이해했으니

이제 본격적으로 어떻게 동작되는지 코딩을 통해 알아보기로 하자. 

 

• 동작과정

위에서 사용한 예시를 그대로 이용하여 설명해보자. 

위와 동일하게 처음 시작 노드는 1, 마지막 목적지는 5로 가정한다.

처음에 노드 1에서 이동할 수 있는 비용은 아직 모두 무한대(inifinity)로 설정한다. 

아직 다음 노드를 방문하지 못했으므로, 모두 무한대로 설정된 상태이다.

 

출발 노드 1번은 0으로 초기화한다. 노드 1과 인접해있는 노드 2, 노드 3, 노드 6의 비용을 각각 갱신한다.

현재 배열에 저장된 값 중 가장 작은 비용을 가진 노드는 2번이므로, 2를 선택한다. 

 

다음에 방문한 노드 2와 인접한 노드 3, 4의 거리를 갱신할 수 있다. 

이 때, 노드 3의 기존 cost는 9이고, 2까지의 최단경로와 2->3의 cost를 더한 값은 7+10=17이다.

더 작은 것을 선택해야 하므로 해당 배열 값은 그대로 내버려둔다.

노드 4의 거리는 1->2->4로 22가 새롭게 갱신된다. 

이미 방문한 노드를 제외한 노드들 중 cost가 가장 적은 노드 3을 방문한다.

 

노드 3과 인접한 4와 6 노드를 갱신할 수 있다.

노드 4는 기존의 cost 22보다 1->3->4, 즉 9+11=20 이 작기 때문에 더 작은 20으로 갱신한다.

노드 6 또한, 기존의 cost 14보다 1->3->2를 통한 cost 9+2=11이 더 적기 때문에 11로 갱신한다.

방문하지 않은 노드 4,5,6 중 가장 적은 cost를 가진 노드 6을 방문한다. 

 

방문하지 않은 노드 5에 대한 가중치를 갱신할 수 있다. 

이로써, 출발 노드 1번에서 도착 노드 5번까지 도달하였으므로 최단경로를 구한 것이 된다. 

또한, 위의 배열은 출발 노드로부터 모든 노드까지 도달하는 데 걸리는 최소 비용 배열이 된다. 

모든 노드를 방문하면 다익스트라 알고리즘이 종료된다. (= infinity에 해당하는 노드가 없음)

 

 

---

Time Complexity

T(n) = 2(n-1)(n-1) = O(n^2)