[알고리즘]다익스트라 최단 경로 알고리즘 개념 부수기 / heap이 뭐야?

다익스트라 최단 경로 알고리즘

정점 한개를 기준으로(=시작 정점) 다른 모든 정점을 도착하는 단일점에서의 최단 경로 알고리즘

• 방향 그래프, 무방향 그래프 모두 적용
• 간선의 가중치가 음수면 다익스트라 알고리즘을 사용할 수 없다.
• 가장 가까운 정점(방문x 정점)을 선택해 추가할 때, 추가된 새로운 정점에 의해 단축되는 경로가 있다면 해당 경로로 최단 경로를 수정하는 알고리즘이다.
• 집합 또는 vertex방문체크를 하면서 최단 경로를 구할 경우( 원래의 알고리즘 ) 시간복잡도는 O(E + V^2) == O(V^2)이다.
• 우선순위 큐를 활용할 경우 시간 복잡도는 O(ElogV)이다.

Algorithm

1. set distance 
2.시작 정점 방문 체크
3. 방문하지 않은 정점 중 시작점과 최소거리인 정점을 찾아 방문체크를 하면서 최소인 거리가 있으면 distance를 새로 갱신! 의 반복

 

출처 : wikimedia.org

기본적으로 다익스트라 알고리즘은 방문하지 않은 V'정점을 집합에 포함시켜가면서 V'와 연결된 다른 정점들의 거리 가중치 합과 기존 distance에 저장된 최단 경로 비용과 min값을 비교해 최단 경로 비용을 갱신해 나가는 알고리즘이다.

예를 들어

시작 정점 = v
새로운 정점 = u 일때
u와 인접한 w 정점이 있다고 가정한다면
distance[w] = min(distance[w], distance[u] + weight[u][w])
새로운 정점까지 가는 비용 + 새로운 점u에서 정점w와 연결된 가중치의 합이 기존 v정점에서 가는 w정점 가중치보다 작다면 최단 거리는 갱신될 것이다.

---

그림1. 그래프

그래프가 주어진다.

그리고 시작 정점이 주어지고, 시작 정점에서 갈 수 있는 모든 정점의 최단 거리를 구할 수 있는게 다익스트라 알고리즘이다.

 

 시작 정점을 A라고 가정한다.

A = {(B,10),(C,5)}

B = {(C,2),(D,1)}

C = {(B,3),(D,9),(E,2)}

D = {(E,4)}

E = {(D,6)}

그래프의 정보는 이런 식으로 구현하면 된다.

 

그리고 visit 배열 Bool형태로 vertex개수만큼 만들고, distance 또한 INF로 초기화를 해서 vertex개수 만큼 만든다. 

1. 시작 정점 A의 방문 처리를 한다.

이때 시작정점의 최소 비용은 0으로 두어야 한다.

 

2. 시작정점(v)에서 정점(u)들을 비교한다.

이때 인접한 정점에 대해서 인접한 정점을 통해 가는 것이 최소 비용인지 아니면 원래 저장된 distance가 최소 비용인지를 구한다.

distance[w] = min(distance[w](시작 정점에서 w정점으로 가는 최단 비용), distance[u](시작정점에서 u로가는 최단비용) + weight[u][w](u정점->w정점으로 가는 가중치) )

 

그 예를 하나만 들자면

A -> B로가는 최단 경로 갱신은

distance[B] = min(distance[B] , distance[A] + weight[A][B])

distance[B] = min(무한대, 0+10) = 10

A정점에 대해 인접한 정점들은 위에 그래프 구성처럼 A 배열의 원소들을 포문으로 받으면 된다.

 

3. visited에 속하지 않은 정점 중 distance가 최소인 정점을 기준으로 인접한 정점을 탐색한다.

C정점이 weight == 5를 차지하므로 C 정점을 기준으로 인접한 정점들을 탐색한다.



2. 3의 방법으로 반복해서 visited가 전부 True처리 된다면 더 이상 갱신할 최단 비용이 없음을 의미하고, A정점으로부터 모든 정점을 다 한번씩 훑었으므로 다익스트라 탐색을 종료한다.

---

 

위 과정을 자세히보면 visited가 막 true 처리된 정점에 대해 인접한 정점들을 전부 훑어야 한다. 따라서 최악의 경우 O(V^2)의 시간복잡도가 발생한다. 물론 탐색 또한 이중 포문을 통해 탐색해 나가야 한다.

 

이 시간 복잡도를 개선시키기 위해서는 우선순위 큐를 활용해야 한다.

우선순위 큐는 Heap의 개념을 사용한다.

간단히 소개하자면 heap이란 완전 이진트리 노드로 구성 되어있는데, 키값이 가장 큰 노드(최대힙) 또는 가장 작은 노드(최소힙)를 찾기 위한 자료구조이다.

 

일반적으로 말하는 힙은 최대힙을 의미하지만 다익스트라의 경우 최소 힙을 통해 우선순위 큐로 활용한다.

시작 노드를 기준으로 인접한 정점의 최소 weight가 최소 힙의 루트로 자리잡게 된다.