[알고리즘] 최단 경로 문제, 다익스트라(Dijkstra)

그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재한다.
가장 유명한 것이 다익스트라(Dijkstra) 알고리즘이다.
해당 글에서는 다익스트라 알고리즘을 다룬다.

 

1. 최단 경로 문제란?

• 간선(Edge)의 가중치(Weight)의 합이 최소가 되는 두 정점(Vertex)(또는 노드) 사이의 경로를 찾는 문제
• 지도상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷하다. 네비게이션 최적 경로 탐색.
  • 정점은 교차로, 간선은 길, 가중치는 거리나 시간과 같은 이동 비용에 해당한다.

 

 

2. 다익스트라 (Dijkstra) 알고리즘이란?

정의

하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘

 

특징

• 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디(Greedy) 알고리즘 중 하나로, 단순할 뿐만 아니라 실행 속도 또한 빠르다.
• 다익스트라 알고리즘은 노드 주변을 탐색할 때 BFS(너비 우선 탐색)을 이용하는 대표적인 알고리즘이다. 
• 가중치가 음수일 경우는 처리할 수 없다.
  • 모든 값을 더해서 양수로 변환하거나, 벨만포드 알고리즘 사용
• 최장 거리를 구할 경우 처리할 수 없다.

 

2-1. 다익스트라 알고리즘 동작 전제

• 다익스트라 알고리즘은 임의의 정점을 출발 집합에 더할 때 그 정점까지의 최단 거리는 계산이 끝났다는 확신을 갖고 더한다.
• 만일 음수로 인해 이후에 더 짧은 경로가 존재한다면 다익스트라 알고리즘의 논리적 기반이 무너지기 때문에 음수는 처리할 수 없다.
• 같은 이유로 최장 거리를 구하는 데에도 다익스트라 알고리즘을 사용할 수 없다.

 

2-2. 다익스트라 시간복잡도

E는 간선, V는 정점.
우선순위큐를 사용하면 효율적이기 때문에 다익스트라 알고리즘을 구현할 때 우선순위 큐를 접목한 형태를 널리 이용한다.

 

• 최초 구현에서 시간복잡도는 O(V^2)이었으나, 현재는 너비우선탐색(BFS)시 가장 가까운 순서를 찾을 때 우선순위큐를 이용하면 시간 복잡도는 O((V+E)logV)가 된다.
• 모든 정점이 출발지에서 도달이 가능하다면 최종적으로 O(ElogV)가 된다.