[Algorithm] 최단 경로 찾기 : 다익스트라 알고리즘

💡최단 경로 찾기?

• 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제이다.

💡어떻게 구할까?

1. 무작위 방법 : 모든 도시들이 다 연결되어 있다면 출발점에서 가능한 경로의 수는 θ(n!)
2. 다익스트라 최단경로 알고리즘
   • 그리디 알고리즘
   • (결과적으로) 출발점에서 가까운 도시부터 차례대로 최단 경로를 탐색
   • 한번 결정된 최단 경로는 절대 바뀌지 않으며 출발점에서 더 먼 도시의 최단 경로를 구할 때 이용

 

 

➰최단 경로 찾기 알고리즘의 종류

1. 단일 시작점 최단 경로 알고리즘 : 출발지점을 하나 선택하면 나머지 다른 모든 지점까지의 최단 경로를 알려주는 유형
2. 모든 쌍 최단 경로 알고리즘 : 모든 지점들간의 최단 경로를 알려주는 유형

최단 경로 찾기 알고리즘은 프림의 최소 신장 트리 알고리즘과 거의 흡사한 과정으로 진행된다.

 

❗️프림 알고리즘과의 2가지 차이점

1. 프림 알고리즘은 임의의 점에서 시작 BUT 다익스트라 알고리즘은 주어진 출발점에서 시작
2. 프림 알고리즘은 트리에 하나의 점(선분)을 추가시킬때, 현재 상태의 트리에서 가장 가까운 점을 추가 BUT 다익스트라 알고리즘은 출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고 그점의 최단 거리를 확정한다.

---

💡다익스트라 알고리즘의 개요 (MST를 구하는 프림 알고리즘과 원리가 거의 동일)

1. 처음부터 끝까지 트리를 유지
   • 출발점을 시작 트리로 초기화하고 매 단계에서 하나의 노드와 간선을 붙여나감
2. 노드를 추가한다 = 그 지점까지의 최단 경로를 한다.
   • 처음에는 최단 경로가 확정된 노드 집합 = {출발 노드}
   • 매 단계마다 하나씩 노드를 늘려가면서 모든 노드들을 포함할 때 까지 반복
3. 욕심쟁이 방법이니 만큼 노드를 선택하는 방법이 핵심
   • 기준 : 출발도시로부터의 최단 경로가 가장 짧은 노드
   • 단, 이미 최단 경로가 밝혀진 노드들만 경유

 

💡다익스트라 알고리즘 - 최단경로 찾기

// ShortestPath(G,s)
// 입력 : 가중치 그래프 G = (V,E), |V| = n, |E| = m
// 출력 : 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D
1. 배열 D를 무한대로 초기화 시킨다. 단, D[s] = 0 으로 초기화한다.
	// 배열 D[v]에는 출발점 s로부터 점 v까지의 거리가 저장된다.
    // 각 점 v에 대해서 D[v]=무한대로 초기화 
2. while(s로부터의 최단 거리가 확정되지 않은 점이 있으면) {
3. 	현재까지 s로부터 최단 거리가 확정되지 않은 각 점 v에 대해서 최소의 D[v]의 값을 가진 점 v(min)을 선택하고,
    출발점 s로부터 점 v(min)까지의 최단 거리 D[v(min)]을 확정
4.  s로부터 현재보다 짧은 거리로 점 v(min)을 통해 우회 가능한 각 점 w에 대해서 D[w]를 갱신
   }
5. return D

• Line 2~4의 while 루프는 (n-1)회 수행됨.
• 현재까지 s로부터 최단 거리가 확정된 점들의 집합을 T라고 하면 V-T는 현재까지 s로부터 최단 거리가 확정되지 않은 점들의 집합.
• 따라서, V-T에 속한 각 점 v에 대해서 D[v]가 최소인 점 v(min)을 선택하고, v(min)의 최단 거리를 확정 시킨다.
  • 즉, D[v(min)] <= D[v], v ∈ V-T 이다.
• '확정한다'는 것의 두가지 의미
  1. D[v(min)]이 확정된 후에는 다시 변하지 않는다.
  2. 점 v(min)이 T에 포함된다.

     

 

🥺공부 흔적

---

💡최단 경로 찾기 - 다익스트라 알고리즘의 시간복잡도

• while 루프가 (n-1)번 반복되고,
  • 1회 반복될 때 line3에서의 최소 D[v]를 가진 점 v(min)을 찾는데 O(n)의 시간이 걸린다. 왜냐하면 배열 D에서 최소값을 찾는 것이기 때문이다.
  • 또한 line 4에서도 v(min)에 연결된 점의 수가 최대 (n-1)개 이므로, 각 D[w]를 갱신하는데 걸리는 시간은 O(n)이다.
• 따라서 시간 복잡도는 (n-1) x {O(n) + O(n)} = O(n^2)이다.

 

응용

• 맵퀘스트와 구글 웹사이트의 지도 서비스
• 자동차 네비게이션
• 네트워크와 통신분야 및 모바일 네트워크
• 산업 공학
• 경영 공학의 운영 연구
• 로봇 공학
• 교통 공학
• VLSI 디자인 분야 등

 

---

Reference 

서울과학기술대학교 컴퓨터공학과 알고리즘 수업