그래프 최단 경로 구하기(다익스트라)

가중치가 있는 그래프에서는 일반적으로 시작 노드에서 끝 노드까지 이동할 때 거치는 간선의 가중치의 총 합이 최소가 되는 것을 말한다. 

 

최단 경로는 구하는 대표적인 알고리즘에는 다음과 같은 두가지 알고리즘이 있다. 

• 다익스트라 알고리즘
• 벨만-포드 알고리즘

 

다익스트라 알고리즘

 

가중치가 있는 그래프의 최단 경로를 구하는 문제는 대부분 다익스트라 알고리즘을 사용한다고 보면 될 정도로 중요한 알고리즘이다. 

 

[다익스트라 알고리즘의 동작 과정]

 

1. 시작 노드를 설정하고 시작 노드로부터 특정 노드 까지의 최소 비용을 저장할 공간과 직전 노드가 뭔지 저장할 공간을 마련한다. 

        1-1. 최소 비용을 저장할 공간은 모두 매우 큰 값으로 초기화 한다.

               (여기서는 무한대(infinite)를 의미하는 약자 INF로 표현할 예정이다. )

        1-2. 시작 노드의 최소 비용은 0이고, 직전 노드는 자기 자신으로 한다. 

2. 해당 노드를 통해 방문할 수 있는 노드 중(아직 방문하지 않은 노드 중), 현재까지 구한 최소 비용이 가장 적은 노드를 선택한다. 

        2-1. 해당 노드를 거쳐서 각 노드까지 가는 최소 비용과 현재까지 구한 최소 비용을 비교하여 작은 값을 각 노드의 최소 비용으로 갱신한다.  

        2-2. 이때 직전 노드로 어떤 노드였는지도 같이 갱신한다. 

3. 노드 개수에서 1을 뺀 만큼 반복한다. 

 

 

 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

---

[관련 의문]

 

Q. 힙큐를써서 현재 구한 최단거리중에 젤 짧은걸 먼저 방문한다 하더라도 결국 모든 노드를 다 방문하는데 힙큐를 왜 쓰는것인가?

A. 힙큐를 쓰는 이유는 효율적으로 최단 경로를 찾기 위해서이다. 필요한 노드만 우선 방문한다. 다익스트라 알고리즘은 가장 짧은 거리의 노드를 우선적으로 방문하고 그 노드의 인접 노드들만 탐색한다. 이렇게 함으로써 필요하지 않은 노드를 최대한 적게 방문할 수 있게 된다.

 

Q. 그럼 예를들어서 힙큐를 사용하지 않으면 결국 모든 노드를 비효율적으로 돌게돼서, 결국 돌아봤자 최단거리가 아닌 경우에는 거리 갱신을 할 필요도 없기 때문에 비효율적으로 돌게 된다는건지?

A. YES

 

힙큐를 사용하지 않는다면, 매번 모든 노드를 확인해서 가장 짧은 거리를 가진 노드를 찾는 과정이 필요하다. O(N)의 시간이 걸리고, 이를 모든 노드에 대해 반복하므로 전체 복잡도가 커진다. 

 

반면, 힙큐를 사용하면 가장 짧은 거리의 노드를 O(log N) 시간에 찾아낼 수 있습다. 이 차이로 인해 노드 수가 많아질수록 힙큐를 사용한 다익스트라 알고리즘이 훨씬 빠르게 동작하게 된다.

 

거리가 확정되지 않은 노드들을 계속 방문하게 됨

 

최단 거리의 노드를 먼저 방문하면 그 주변 노드들의 거리가 효율적으로 갱신되지만, 힙큐 없이 임의의 노드를 방문한다면 거리가 확정되지 않은 상태로 노드를 계속 방문하는 일이 발생한다. 이렇게 되면 사실상 거리 갱신이 필요 없는 노드들도 방문하게 되고, 결국 불필요한 계산과 방문이 계속 일어난다.