최단거리 알고리즘 ❶ Dijkstra Algorithm

크으으... 므시써

(뭐 대충 중요하다는 내용ㅎ)

 

최단 경로 문제를 풀 때 가장 많이 언급되고 활용되는 삼대장이 있죠?

• 다익스트라
• 벨만포드
• 플로이드

상황에 맞게 위 알고리즘을 적용해서 문제를 해결하면 될텐데 언제, 무엇을 선택할 지 모르겠다면 3가지를 떠올려봅시다. 문제를 그래프화 하는 것에 성공하셨다면 이제 이 3가지 흐름을 생각해 봅시다.

1. 가중치가 있는가? : 가중치가 없다면 BFS로 해결 가능
2. 음수간선이 있는가? : weight에 음수 값이 있다면 벨만포드
3. 단일 시작점을 갖는가? : 단일 시작점이 주어진다면 다익스트라, 모든 정점들의 쌍에 대한 경로 값을 알고 싶다면 플로이드

어떤 알고리즘을 쓰면 되는지 선택하셨다면 각 알고리즘들의 개념을 짚어보도록 하겠습니다. 오늘은 Dijkstra Algorithm에 대해 먼저 살펴보도록 하죠.

The Dijkstra Algorithm

• 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산
• BFS의 연장선상에서 고안 된 알고리즘이라 매우 형태가 유사
  • 차이점 : Dijkstra는 Priority Queue를 사용한다는 점
  • 특정 노드의 이웃(neighbor)을 살피지만, 시작점 부터의 거리가 가장 짧은 것 부터 살피는 특징을 갖고 있음

직접 해보기

아래와 같은 그래프가 주어졌다고 생각 해봅시다. Dijkstra를 통해 문제를 풀 경우 우측의 표와 같이 방문 여부, 시작점부터의 거리, 그리고 경로에 놓인 노드 들에 대한 정보를 트래킹 할 수 있게끔 구현한다고 생각하면 수월합니다.(...본인 말에 책임 못지는 편 *^^*)

방문여부, 시작점부터의 거리, 경로에 놓인 노드

어떤 과정으로 저 표가 채워나갈지 살펴보기 전에 표가 채워져 나가는 방법 부터 살펴봐야겠죠? 이것도 딱 3가지만 기억하면 되는데, 표를 채우는 로직이 실제 구현 로직이 되니 실구현할 때도 이 3가지만 기억하면 되겠네요. (분명 아까 위에도 표에 3가지 들어간다고 한 것 같은데....ㅎ)

1. 노드 선택 기준 = 방문하지 않은 노드 중 시작점에서부터의 거리가 가장 짧은 것
2. 꺼낸 노드의 이웃 보기
3. 이웃들 경로 갱신 = 새로운 경로 < 기존 경로 일 때

이제 어떤식으로 표가 채워지는지 알았으니 위 그래프에 대한 문제를 조금 더 구체화 시켜 보겠습니다. Dijkstra는 단일 정점에서부터의 최단 경로를 구하므로 시작 정점이 주어져야 합니다. 시작 정점 = A라고 해볼게요. 해당 조건이 주어지면 아래 표처럼 초기화 할 수 있습니다.

방문하지 않은 노드 중 시작점에서부터 거리가 가장 짧은 노드 = A

• 선택 노드 = A (0, ∞, ∞, ∞, ∞) → A 방문 = true로 변경

• A의 이웃 =  B, D

• B와 D는 모두 새로운 경로가 현재 경로보다 작으므로 시작점부터의 거리 및 최단 경로에 놓인 노드 갱신

다음에 선택 될 노드는 거리가 1로 가장 작은 D가 되겠네요.

 

• 선택 노드 = D → D 방문 = true 로 변경
• D의 이웃 = B, E (A는 방문이 완료되었으므로)
• B의 (현재 경로 = 3) < (새로운 경로 = 5) 이므로 갱신하지 않음
  E는 새로운 경로가 현재 경로보다 작으므로 시작점부터의 거리 및 최단 경로에 놓은 노드를 갱신

이렇듯 모든 과정을 진행해주면 됩니다.

 

Pseudo Code로 맛보기

function Dijkstra (Graph: g, source: s) :
     create vertex set Q // 미방문 노드가 모여있을 Q

     // 초기화 진행 중 삐비빕...
     for each vertex v in Graph g: 
          distance[v] = ∞
          prev[v] = undefined
          add v to Q
     distance[s] = 0

     while Q is not empty:
          // 살펴 볼 노드는 미방문 & 거리가 가장 짧아야 함
          u = vertex in Q with min distance[u]
          remove u from Q

          // 거리 계산해보고 필요 시 업데이트
          for each neighbor v of u:
               new_distance  = distance[u] + weight(u, v)
               if new_distance < distance[v] :
                    distance[v] = new_distance
                    prev[v] = u

시간복잡도

Dijkstra 알고리즘의 시간 복잡도에 관여하는 요소는 총 2가지가 있습니다.

• 간선(Edge) 검사

• Priority Queue에 삽입/삭제

첫 번째 요소는 BFS와 유사하게도 각 정점은 정확히 한 번 방문하기 때문에 모든 Edge는 한 번씩만 검사하므로 O(|E|)가 됩니다. Priority Queue는 조금 나눠서 생각 해봐야 합니다. 

먼저, Priority Queue에 추가되는 원소의 최대 갯수는 E개 입니다. 그리고 Heap 자료구조를 사용하는 Priority Queue에서 삽입과 삭제에 소요되는 시간은 O(lgE)이므로 시간복잡도는 O(|E| lg|E|)가 됩니다.

두 요소를 합하면 역시 O(|E| lg|E|)가 될텐지만 |E| < V² 이므로 최종적으로 시간복잡도는 O ( |E| lg|V| ) 로 나타낼 수 있습니다.

문제를 뽀샤버려라

Dijkstra와 관련 된 문제를 풀어보고 싶다면 아래 링크들, 번호들, ID들 확인해보시면 될 것 같습니다.

• 백준 다익스트라 모음 : 열로가쑈
• 프로그래머스 : 배달(12978), 가장 먼 노드(49189)
• 알고스팟 : 신호 라우팅(ROUTING), 소방차(FIRETRUCKS), 철인 N종 경기(NHTHLON)