노트

다익스트라 알고리즘

Dijkstra's Algorithm

CS#algorithm · 연결된 개념 5개

쉽게 말하면

다익스트라는 내비게이션처럼 출발지에서 가장 가까운 곳부터 '여기까진 이 길이 최단'이라고 하나씩 확정해 가는 방식이에요. 확정한 곳을 거쳐 더 짧게 가는 길이 보이면 거리 기록을 고쳐 써요.

비유가 깨지는 곳 다익스트라는 간선 비용이 음수가 아니라고 믿고 확정해요. 지나가면 오히려 거리가 줄어드는 음수 간선이 있으면 이미 확정한 답이 틀려져서, 그때는 벨만-포드를 써요.

간선에 음수가 아닌 가중치(거리·비용·시간)가 있는 그래프에서, 한 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘. 에츠허르 데이크스트라(Edsger W. Dijkstra)가 1956년에 고안했다. 지도 길찾기와 네트워크 라우팅의 바탕이다.

방식

  1. 시작 정점의 거리는 0, 나머지는 무한대로 둔다
  2. 아직 확정되지 않은 정점 중 거리가 가장 짧은 것을 꺼낸다
  3. 그 정점의 이웃마다 "꺼낸 정점까지 거리 + 간선 가중치"가 지금 아는 거리보다 짧으면 갱신하고, 어디서 왔는지(이전 정점)를 기록한다
  4. 모든 정점이 확정될 때까지 2~3을 반복한다
  5. 이전 정점 기록을 끝에서부터 거슬러 올라가면 경로가 나온다
// 2단계의 "가장 짧은 것 꺼내기"를 우선순위 큐로
pq.enqueue(start, 0)
while (!pq.isEmpty()) {
  const { value: v, priority: d } = pq.dequeue()
  if (d > dist[v]) continue // 이미 더 짧은 길을 찾은 낡은 항목
  for (const { node, weight } of graph[v]) {
    const nd = d + weight
    if (nd < dist[node]) { dist[node] = nd; prev[node] = v; pq.enqueue(node, nd) }
  }
}

복잡도

2단계를 매번 전체 훑기로 하면 O(V²), 우선순위 큐(이진 힙)로 하면 O((V + E) log V)다.

  • 음수 가중치가 있으면 틀린 답을 낸다. 그때는 벨만-포드 알고리즘(Bellman-Ford Algorithm)을 쓴다
  • 가중치가 모두 같다면 더 단순한 너비 우선 탐색 (BFS)로 충분하다
  • 목적지 방향으로 추정치를 더해 탐색 범위를 줄이면 A* 알고리즘(A* Search Algorithm)이 된다

그래프 표현은 그래프, 이미 확정한 결과를 재사용한다는 점에서 동적 프로그래밍과도 닮았다.

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 이진 탐색 트리

    각 노드가 자식을 최대 둘 가지고, 왼쪽 서브트리의 모든 값은 노드보다 작고 오른쪽은 크다는 규칙을 지키는 트리. 비교할 때마다 한쪽 가지를 버리므로 정렬된 데이터를 빠르게 찾고 넣을 수 있다.

  • 깊이 우선 탐색 (DFS)

    그래프에서 한 갈래를 갈 수 있는 데까지 깊이 들어갔다가, 막히면 되돌아와(백트래킹, Backtracking) 다른 갈래로 가는 탐색. 방문한 정점은 기록해 다시 가지 않는다.

  • DB 인덱스와 트레이드오프

    DB 인덱스는 특정 컬럼 값으로 행을 빨리 찾도록 테이블 옆에 따로 유지하는 보조 자료구조(auxiliary data structure)다. 관계형 DB의 기본 인덱스는 정렬된 균형 트리(B-tree 계열)라서, 전체를 훑지 않고 트리를 따라 내려가 원하는 행에 닿는다.

  • 정렬 알고리즘

    컬렉션의 원소를 어떤 순서(크기, 사전순, 날짜…)로 다시 배치하는 알고리즘. 같은 일을 하는 방법이 여럿이고 각자 강점이 달라, 트레이드오프를 익히기 좋은 주제다.

  • 빅오 표기법

    입력 크기 n이 커질 때 알고리즘의 실행 시간(시간 복잡도, Time Complexity)이나 메모리(공간 복잡도, Space Complexity)가 얼마나 빨리 늘어나는지를 대략적으로 나타내는 표기. 정확한 횟수가 아니라 증가하는 모양을 본다. 그래서 상수와 작은 항은 버린다(2n + 5는 O(n)).

보기 옵션