[Algorithm] Dijkstra's Algorithm ( 다익스트라 알고리즘 )

최단 경로 문제 (Shortest path problem) 

가중치가 있는 그래프에서 한 정점에서 다른 정점까지 갈 수 있는 최단 경로를 구하는 문제이다. 

 

s 에서 t로 갈 때 지나가는 경로 상에 있는 cost의 합이 최소화 되는 경로를 찾는 경우이다. 최단경로 문제는 Internet packet routing, flight reservation, driving directions 등 다양한 경우에 사용된다. 

최단경로 문제를 해결하는 방법은 여러가지가 있는데 그 중에 대표적인 것은 아래 세 가지이다.

• 다익스트라 알고리즘 (Dijkstar's algorithm)
• 플로이드-와샬 알고리즘 (Floyd Warshall algorithm)
• 벨만 포드 알고리즘 (Bellman Ford algorithm)

오늘은 이 중 다익스트라 알고리즘이 무엇인지 정리해 보았다. 

 

2023.05.24 - [Computer Science/Data structure & Algorithm] - [algorithm] Floyd-Warchall algorithm

[algorithm] Floyd-Warchall algorithm

 

 

 

Dijkstar's algorithm

다익스트라는 single-source shortest-paths problem을 해결할 때 사용한다.

조건

1. 가중치가 있는 방향그래프이다.
2. 모든 정점의 가중치는 음수가 아니다.

 

동작 과정

문제 상황은 아래와 같다. visited set과 unvitied set, cost array를 만든다. A에서 F로 가는 최단 경로를 구한다고 하자.

1. 모든 노드들을 unvisited 상태로 표시한다. 모든 노드들을 unvisited set에 저장한다.

2. initial node를 방문하고 initial node에서의 거리 값을 표시한다. initial node 는 0으로 한번에 도달하지 못하는 노드는 INF 로 설정한다.

 

3. 방문하지 않은 노드 중 가장 비용이 낮은 노드로 이동한다. (우리 문제 상황에서는 C에 해당한다)

4. A에서 각 노드를 가는 경우와 A에서 C를 거쳐 각 노드를 가는 경우를 비교해 더 작은 값을 취한다.

=> E를 보면 A -> E : INF , A -> C -> E : 2 + 3 = 5이다. 즉, min(cost[E],cost[C] + 3) 을 취하면 된다.

 

5. 모든 정점을 방문할 때 까지 3~4의 과정을 반복한다.

[B 방문]

[E 방문]

 

[D 방문]

 

[F 방문]

 

모든 정점을 방문을 완료했다. 이때, 만들어진 표가 A에서 각 정점으로 갈 때의 최소 비용이다. 

 

구현

알고리즘 교과서에 나온 슈도코드는 아래와 같다.

---

---

 

시간 복잡도

최악의 경우 : N개의 노드가 있을 때 첫 번째 노드에서 N-1번의 연산이 일어나고 두 번째 노드에서도 N-1의 연산이 일어나는 경우이다. (양방향 모두 고려한다고 했을 때) 이런 경우 N * ( N-1) 의 연산이 일어난다.

=> O(n^2)

priority queue(우선순위 큐)를 사용한다면 알고리즘 작동 시간을 향상시킬 수 있다. 그래도 연산 횟수가 줄어들지는 않기에 최악의 경우 O(n^2logn)의 효율성을 가진다.

 

다익스트라의 가장 큰 단점은 비용이 양수가 아닌 음수인 경우 무한 루프에 빠지는 등 작동이 제대로 되지 않는다. ( 그래서 가정에 모든 WEIGHT가 양수라는 조건이 있었다. )