다익스트라 알고리즘 완전 정복: 그래프 최단 경로 계산 원리와 단계별 예제

다익스트라 알고리즘이란?

다익스트라 알고리즘(Dijkstra's Algorithm)은 연결된 그래프에서 특정 노드, 즉 소스(source) 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 실행 결과로 소스 노드를 루트(root)로 하는 최단 경로 트리(shortest path tree)가 생성됩니다. 이 알고리즘은 1956년 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)가 고안했으며, 오늘날 컴퓨터 네트워크에서 라우팅 비용을 최소화하는 최적 경로를 산출하는 데 폭넓게 활용되고 있습니다. 대표적인 응용 분야로는 OSPF 같은 네트워크 라우팅 프로토콜이나 지도 서비스의 길찾기 기능 등이 있습니다.

알고리즘 개요

입력 − 네트워크를 나타내는 그래프와 소스 노드 s
출력 − s를 루트 노드로 하는 최단 경로 트리 spt[]

1. 초기화 단계

• 크기가 |V|(노드 수)인 거리 배열 dist[]를 준비하고, dist[s] = 0, dist[u] = ∞(무한대)로 설정합니다. 여기서 u는 s를 제외한 그래프의 모든 노드를 의미합니다.
• 그래프의 모든 노드를 담고 있는 배열 Q를 만듭니다. 알고리즘이 끝나면 Q는 비어 있게 됩니다.
• 방문한 노드를 추가할 빈 집합 S를 준비합니다. 알고리즘이 끝나면 S에는 그래프의 모든 노드가 포함됩니다.

2. 반복 단계 (Q가 빌 때까지)

• Q에서 dist[u] 값이 가장 작으면서 아직 S에 속하지 않은 노드 u를 꺼냅니다. 첫 번째 반복에서는 dist[s]가 가장 작으므로 소스 노드가 선택됩니다.
• u를 S에 추가하여 방문 처리를 합니다.
• u에 인접한 모든 노드 v에 대해 다음 조건을 검사하여 dist[v]를 갱신합니다.
  • 만약 (dist[u] + 간선 u-v의 가중치) < dist[v]라면,
    → dist[v] = dist[u] + 간선 u-v의 가중치로 업데이트합니다.

알고리즘이 종료되면 배열 dist[]에는 소스 노드 s에서 다른 모든 노드까지의 최단 거리가 저장됩니다.

예제로 살펴보는 동작 과정

알고리즘의 동작은 실제 예제를 통해 가장 잘 이해할 수 있습니다. A부터 G까지 7개의 노드가 가중치 있는 간선으로 연결된 다음 그래프를 생각해 보겠습니다.

초기 상태는 다음과 같이 설정됩니다.

• dist[7] = {0, ∞, ∞, ∞, ∞, ∞, ∞}
• Q = {A, B, C, D, E, F, G}
• S = ∅ (빈 집합)

패스 1 — 노드 A 선택

Q에서 dist[] 값이 0으로 가장 작은 A를 선택해 S에 넣습니다. A의 인접 노드는 B와 C이며, 알고리즘 규칙에 따라 두 노드의 dist[] 값을 갱신합니다.

• dist[7] = {0, 5, 6, ∞, ∞, ∞, ∞}
• Q = {B, C, D, E, F, G}
• S = {A}

이 시점까지의 거리와 최단 경로는 다음과 같습니다. 초록색 노드는 이미 S에 추가된 노드를 의미합니다.

패스 2 — 노드 B 선택

dist[] 값이 5로 가장 작은 B를 선택해 S에 넣습니다. B의 인접 노드는 C, D, E이며, 세 노드의 dist[] 값을 갱신합니다.

• dist[7] = {0, 5, 6, 12, 13, ∞, ∞}
• Q = {C, D, E, F, G}
• S = {A, B}

패스 3 — 노드 C 선택

dist[] 값이 6으로 가장 작은 C를 선택해 S에 넣습니다. C의 인접 노드는 D와 F이며, 두 노드의 dist[] 값을 갱신합니다.

• dist[7] = {0, 5, 6, 8, 13, 10, ∞}
• Q = {D, E, F, G}
• S = {A, B, C}

패스 4 — 노드 D 선택

dist[] 값이 8로 가장 작은 D를 선택해 S에 넣습니다. D의 인접 노드는 E, F, G이며, 세 노드의 dist[] 값을 갱신합니다.

• dist[7] = {0, 5, 6, 8, 10, 10, 18}
• Q = {E, F, G}
• S = {A, B, C, D}

패스 5 — 노드 E 선택

E와 F가 모두 dist[] 값이 10으로 가장 작으므로 둘 중 아무거나 선택할 수 있습니다. 여기서는 E를 선택해 S에 넣습니다. E의 인접 노드는 G이며, G의 dist[] 값을 갱신합니다.

• dist[7] = {0, 5, 6, 8, 10, 10, 13}
• Q = {F, G}
• S = {A, B, C, D, E}

패스 6 — 노드 F 선택

dist[] 값이 10으로 가장 작은 F를 선택해 S에 넣습니다. F의 인접 노드는 G인데, F를 경유하는 거리가 기존 dist[G] 값보다 크므로 값은 그대로 유지됩니다.

• dist[7] = {0, 5, 6, 8, 10, 10, 13}
• Q = {G}
• S = {A, B, C, D, E, F}

패스 7 — 마지막 노드 G 처리 후 종료

Q에는 노드가 하나(G)만 남아 있습니다. 이 노드를 Q에서 꺼내 S에 넣으면 되며, dist[] 배열은 더 이상 바뀔 필요가 없습니다. 이제 Q가 비었고 S에 모든 노드가 포함되었으므로 알고리즘이 종료됩니다. 마지막으로 어떤 최단 경로에도 사용되지 않는 간선들을 모두 제거하면, 소스 노드 A에서 다른 모든 노드까지의 최단 경로 트리가 완성됩니다.