다익스트라(Dijkstra)

• 최초작성일 [2020.01.14]

• 1차 수정일 [2020.01.16] - 다익스트라 알고리즘의 시간복잡도 정리

• 2차 수정일 [2020.01.19] - 우선순위 큐로 구현했을 때 시간복잡도 수정 + 다른 구현방법 첨부

아래와 같이 간선에 가중치가 부여된 두 그래프에서 정점 A와 B의 최단 경로를 선택하는 방법은 무엇일까?

BFS(Breadth First Search) 알고리즘은 그래프 내 모든 간선의 가중치가 동일하다는 가정 하에 두 정점 사이의 최단경로를 구하는 알고리즘이므로 위 그래프에서 최단 경로를 찾기에는 적절하지 않다. 이 때 사용할 수 있는 알고리즘이 다익스트라(Dijkstra) 알고리즘이다.

다익스트라 알고리즘은

• 간선에 가중치가 존재하는 그래프에서

• 1개의 정점에서 각 모든 정점과의 최단 거리를 구할 때

사용하는 알고리즘이다.

Edge Relaxation

w(u, v)가 정점 u와 v 사이의 가중치를 나타낸다고 하자. 출발정점이 A라고 할 때,

w(A, B) = min(w(A, C) + w(C, B), w(A, C))

라고 할 수 있다.

BFS 알고리즘에서 dist[v]는 출발 정점에서 v 까지의 최단 경로를 저장하는 자료구조로, 값이 한 번 결정되고 나면 바뀌지 않았다. 하지만 다익스트라 알고리즘에서 dist[v]의 값은 정점을 탐색하면서 변경될 수 있으며, dist[v]에 저장되는 값은 출발 정점과 v사이의 최단 거리와 같거나 클 수 있다. 이렇게 정점을 탐색하면서 두 정점 사이의 최단거리를 찾아내는 과정을 edge relaxation(변 경감)이라고 한다.

def relax(u, v):
  if dist[v] > dist[u] + w(u, v):
    dist[v] = dist[u] + w(u, v)
    prev[v] = u

정점 v1와 v2 사이에 있는 정점 u를 경유할지 말지 여부는 relax(u, v)를 통해 알 수 있다. (여기서 dist[u]는 출발 정점과 u의 최단거리인 것으로 이미 확정된 상태다.)

dist[v2] 가 dist[u] + w(u, v2) 보다 클 경우에는 u를 경유해야 하며 그렇지 않으면 경유하지 않는다.

prev[v]는 v 이전에 방문했던 정점을 나타낸다.

Dijkstra Algorithm

위 그래프에서 edge relaxation을 통해 출발 정점 S와의 최단 거리가 확정된 정점은 S, A, D에 해당한다. dist[B]는 w(D, B)를 알기 전 까지는 확정할 수 없으며, dist[C]도 w(D, C)를 알기 전 까지 확정할 수 없다.

S, A, D와 같이 이미 출발 정점과의 최단 거리가 확정된 정점들을 known region이라고 하며 하나의 집합으로 묶을 수 있다. 정점들을 순회하면서 relaxation을 통해 출발 정점과의 최단 거리가 확정될 때 이 집합에 추가되며, 집합에 가장 처음으로 추가되는 정점은 S 자기자신이다.

이미 최단 거리가 확정된 정점들을 가지고 다른 정점들의 최단 거리를 계산할 때, relaxation이 최대한 적은 빈도로 발생하는 게 효율적일 것이다. relaxation이 최대한 적게 발생하도록 하려면 known region에서 dist가 제일 작은 정점과 인접한 것들을 우선으로 탐색해야 한다. 따라서 known region은 우선순위 큐로 구현한다.

다익스트라 알고리즘에서 각 정점의 최단 거리가 결정되는 과정

위 과정을 코드로 구현하면 아래와 같다.

from math import inf


def dijkstra(G, start):
  dist = [inf for _ in range(len(G))]
  dist[start] = 0
  known_region = list()
  q = list()
  
  # 큐에 모든 정점의 번호를 삽입.
  for v in G:
    q.append(v)
  
  while q:
    # dist가 가장 작은 정점을 큐에서 꺼냄.
    min_dist = min([x for x in dist if x not in known_region])
    min_v = dist.index(min_dist)
    q.remove(min_v)
    
    # 인접한 정점의 dist를 갱신한다.
    for adj_v in adjacent_list(min_v):
      relax(dist, min_v, adj_v)
    
    known_region.append(min_v)


def relax(dist, u, v):
  if dist[v] > dist[u] + weight(u, v):
    dist[v] = dist[u] + weight(u, v)
    prev[v] = u        

시간복잡도

다익스트라 알고리즘의 시간복잡도는 기본적으로

|V| * {T(min(queue)) + T(relax(u, v))}

이다.

• 큐 안에서 dist가 가장 작은 정점을 찾는 데에는 큐에 있는 정점의 갯수만큼 시간이 소요된다. => O(min(q)) = O(|V|)

• 각 정점과 인접한 정점들을 edge relaxation한다. => O(relax(u,v)) = O(|E|/|V|)

min(q)와 relax(u, v)는 정점의 갯수만큼 실행되므로 시간복잡도는 |V| * O(|V| + |E|/|V|) = O(|V|^2 + |E|) = O(|V|^2) 이다. densed graph일 경우 대부 |E|가 |V|의 제곱이므로 시간복잡도는 여전히 O(|V|^2)이다.

  while q:
    # 큐에서 최소값을 찾는 데 최대 |V|만큼 소요.
    min_dist = min([x for x in dist if x not in known_region])
    min_v = dist.index(min_dist)
    q.remove(min_v)
    
    # 정점 1개 당 평균적으로 |E|/|V| 만큼 relax() 수행.
    for adj_v in adjacent_list(min_v):
      relax(dist, min_v, adj_v)
    
    known_region.append(min_v)

만약 큐가 힙 트리를 이용한 우선순위 큐로 구현되어 있다면 시간복잡도는 어떻게 될까?

  from queue import PriorityQueue
  
  q = ProirityQueue()
  ...
  
  while q:
    # 큐에서 최소값을 찾는 데 최대 log 2 |V|만큼 소요.
    min_v = q.pop()    
    
    # 정점 1개 당 평균적으로 |E|/|V| 만큼 relax() 수행.
    for adj_v in adjacent_list(min_v):
      relax(dist, min_v, adj_v)
      q.change_priority()

최소 힙 트리에서 최소값(루트)를 삭제하고, 다음 최소값을 루트에 승격시키는 데 log2|V|만큼 소요된다. 따라서 시간복잡도는 O(log|V|)이다. relax가 한번 이뤄지고 나서는 정점의 dist가 변경되기 때문에 우선순위를 바꿔야 한다. 이 때의 시간복잡도 또한 O(log|V|)이다. 따라서 우선순위 큐를 사용했을 때 시간복잡도는 |V| * O(log|V| + |E|/|V| * log|V| ) = O(|V| * log|V| + |E| * log|V|) 이다.

큐의 2가지 형태를 비교해봤을 때 그래프 내 정점의 갯수가 많을수록 우선순위 큐를 사용하는 게 더 효율적임을 알 수 있다.

큐에 pop/push 연산 없이 change_priority()를 수행하는 빌트인 함수가 파이썬에는 없다. 따라서 처음부터 큐에 모든 정점을 삽입하지 않고 다익스트라를 구현하는 방법을 쓰는 게 낫다. (여기 참고)

출처

• 코세라 알고리즘 강