Dijkstra algorithm

Dijkstra

다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 컴퓨터 과학자 에츠허르 다익스트라가 1956년에 고안했으며 삼 년 뒤에 발표했다.

다익스트라의 슈도코드는 아래와 같다

pseudo code

function Dijkstra(Graph, source):

  create vertex set Q
  
  for each vertex v in Graph:   // 초기화
    if dist[v] then
      dist[v] ← distance
    else
      dist[v] ← INFINITY    // 소스에서 v까지의 아직 모르는 길이
    add v to Q    // 모든 노드는 초기에 Q에 속해있다 (미방문 집합)
    
  dist[source] ← 0    // 소스에서 소스까지의 길이
  
  while Q is not empty:
    u ← vertex in Q with min dist[u]    // 최소 거리를 갖는 꼭짓점
    
    remove u from Q
    
    for each neighbor v of u:   // v는 여전히 Q에 있다.
      alt ← dist[u] + length(u, v)
      if alt < dist[v]:   // v 까지의 더 짧은 경로를 찾았을 때
        dist[v] ← alt
        prev[v] ← u
        
  return dist[], prev[u]

알고리즘

시작할 꼭짓점은 초기점으로, 꼭짓점 Y의 거리를 초기점에서 Y까지의 거리로 정의한다. 다익스트라 알고리즘은 초기 거리 값을 부여하고, 단계를 거듭하며 개선시킬 것이며, 이 개선시키는 것을 간선 완화(edge relaxation)이라고 한다.

1. 모든 꼭짓점을 미방문 상태로 표시한다. 미방문 집합이라는 모든 미방문 꼭짓점의 집합을 만든다.
2. 모든 꼭짓점에 시험적 거리 값을 부여한다: 초기점을 0으로, 다른 모든 꼭짓점을 무한대로 설정한다. 초기점을 현재 위치로 설정한다.
3. 현재 꼭짓점에서 미방문 인접 꼭짓점을 찾아 그 시험적 거리를 현재 꼭짓점에서 계산한다. 새로 계산한 시험적 거리를 현재 부여된 값과 비교해서 더 작은 값을 넣는다. 예를 들어, 현재 꼭짓점 A의 거리가 6이라고 표시되었고, 인접 꼭짓점 B로 연결되는 변의 길이가 2라고 한다면, A를 통한 B까지의 거리는 6 + 2 = 8이 된다. 이전의 B까지의 거리가 8보다 컸다면 8로 바꾸고, 그렇지 않다면 그대로 놔둔다.
4. 만약 현재 꼭짓점에 인접한 모든 미방문 꼭짓점까지의 거리를 계산했다면, 현재 꼭짓점을 방문한 것으로 표시하고 미방문 집합에서 제거한다. 방문한 꼭짓점은 이후에는 다시 방문하지 않는다.
5. 두 꼭짓점 사이의 경로를 찾는 경우: 도착점이 방문한 상태로 표시되면 멈추고 알고리듬을 종료한다.
6. 완전 순회 경로를 찾는 경우: 미방문 집합에 있는 꼭짓점들의 시험적 거리 중 최솟값이 무한대이면 이는 출발점과 미방문 집합 사이에 연결이 없는 경우이므로 멈추고 알고리즘을 종료한다.
7. 아니면 시험적 거리가 가장 작은 다음 미방문 꼭짓점을 새로운 “현재 위치”로 선택하고 3단계로 되돌아간다.

경로를 계획하고 있을 때, 사실은 위에서 했던 것처럼 도착점이 “방문”한 상태가 될 때 까지 기다릴 필요가 없다: 도착점이 “미방문” 꼭짓점들 중 가장 시험적 거리가 작아지면 (그리고 다음 “현재 위치”로 선택될 수 있다면) 알고리즘을 종료할 수 있다.

시간복잡도

하나의 노드에 대해 다익스트라 알고리즘을 수행하는 경우를 따져보겠습니다. 미방문노드 가운데 거리가 가장 작은 노드에 BFS를 적용합니다. 거리를 가장 작은 미방문노드를 가려내려면 최악의 경우 노드 전체를 모두 따져봐야 하므로 O(|V|)입니다. 선택된 노드의 모든 이웃노드들에 대해 최단경로 정보를 업데이트합니다. 한 노드당 엣지의 기대값은 |E|/|V입니다.

다익스트라 알고리즘은 이러한 연산을 전체 노드 수만큼 반복하므로 전체적인 계산복잡성은 O(|V|2+|E|)가 됩니다. 보통의 dense graph는 엣지의 수가 노드 수의 제곱만큼 있으므로 간략하게 계산복잡성을 적으면 O(|V|2)이 됩니다.

제약사항

Dijkstra는 음의 가중치를 간진 간선을 사용하지 못한다. 이유는 아래 블로그가 설명이 잘 되있어서 대신하겠습니다.

최단 경로 문제: 다익스트라 알고리즘과 벨만-포드 알고리즘