내일배움캠프 103일차 - 자료구조 & 알고리즘 20주차 : 다익스트라(Dijkstra)
다익스트라(Dijkstra)
 |
| 교차로 = 점, 도로 = 선. 그런데 도로마다 걸리는 시간이 다름. |
간선에 붙은 이 숫자가 가중치(weight). 우리가 원하는 건 "총 시간 최소" 이다.
Queue를 딱 하나만 업그레이드 하면?
BFS는 "환승 횟수 최소"였다. 모든 도로를 똑같은 1단계로 세기 때문이다.
"총 시간 최소"를 풀려면, BFS의 큐(FIFO)를 "가장 짧은 거리부터 꺼내는" 큐로 바꿔야 한다.
큐(FIFO) 먼저 온 순서대로 → 업그레이드 → 우선순위 큐 가장 가까운 순서로
이것이 에드거 다익스트라가 제안한, 가중치를 사용한 최단 경로, 다익스트라(Dijkstra)이다.
다익스트라의 원리
1) 가중치가 생기면, 왜 BFS가 무너지는가?
간선 옆 숫자가 가중치이다. - BFS로 A에서 C까지의 최단 거리를 구하면 어떻게 되는가?
 |
| 위로 두 칸(1+1) 아래로 직통 한 칸(10) |
같은 목적으로 향하는 경로. BFS의 눈에는 어느 쪽이 먼저 우선적일까?
BFS의 답
: A-C 직통(간선 1개)
= 거리 10
실제 최단
A->B->C (간선 2개)
= 거리 2
BFS는 간선 개수만 세니까, 간선 1개(거리 10)를 간선 2개 (거리2) 보다 가깝다고 착각한다.
이럴 때 바로 "확정(confirm)"이라는 개념이 필요하다.
2) 다익스트라는 두 단계만 반복
정점마다 "지금까지 알려진 최단 거리"를 들고 있다. 처음엔 출발점만 0, 나머지는 전부 ∞.
1. 확정
: 아직 확정 안된 정점 중, 거리가 가장 작은 것을 골라 확정.
2. 갱신
: 확정된 정점을 거치는 길이 더 짧으면 이웃의 거리를 줄임.
이렇게 모든 정점이 확정될 때까지 반복하면 된다.
2-1) 다익스트라 예시
시작)
거리: A=0, B=∞, C=∞, D=∞, E=∞
출발점 A만 0, 나머지는 아직 가는 길을 모르니 ∞.
단계1)
거리: A=0, B=1, C=4, D=∞, E=∞
미 확정 중 최소는 당연히 A(0) → 확정.
A를 거치면 B는 0+1=1 → 갱신.
A를 거치면 C는 0+4=4 → 갱신.
단계2)
거리: A=0, B=1, C=4, D=3, E=∞
미확정 중 최소 = B(1) → 확정.
B를 거치면 D는 1+2=3 → 갱신.
단계3)
거리: A=0, B=1, C=4, D=3, E=8
미확정 중 최소 = D(3) → 확정.
D를 거쳐 C로 가면 3+3=6 > 4 → 갱신하지 않음(빨간 점선)
D를 거쳐 E로 가면 3+5=8 → 갱신.
※ "더 짧은 때만 갱신"한다.
완성)
: 확정 순서가 곧 거리 순서이다.
확정 순서: A → B → D → C → E
거리 순서: 0 → 1 → 3 → 4 → 8 (가까운 것부터 차례로)
2-2) 확정한 거리는 왜 안 바뀔까?
D를 3으로 확정하는 순간, "나중에 더 짧은 길이 나오면 어떻하나?" 라는 걱정이 들 수 있을 것이다.
하지만 그런 길은 없다.
남은 정점은 모두 3보다 멀리 있고, 거기서 D로 더 가면 거리는 늘어가기만 하기 때문.
"지금 가장 가까운 것을 고르고, 되돌아보지 않는다"는 방법이 그리디.
가까워 보이는 것만 고르는 것이 정답은 아니지만. 음수 간선만 없으면 다익스트라에선 언제나 옳다.
3) 매번 전부 훑는 건 아깝다.
방금 구현의 약점, 매 단계 "미확정 중 최소"를 찾으려고 모든 정점을 훑는다.
V번 반복하면 전체 O(V^2) - 정점이 수만 개면 부담.
"어떤 자료구조를 꺼낼 것인가?" → 필요한 건 "최소값을 빠르게 꺼내는" 도구.
큐: 먼저 온 순 → BFS의 큐: 한 층 씩 = 가까운 순 → 우선순위 큐: 항상 최소 거리 먼저
"줄 세우기"가 먼저 온 순서에서 가장 가까운 순서로 변화.
4) 작은 트릭 - 낡은 항목은 무시
같은 정점이 갱신될 때마다 큐에 여러번 들어갈 수 있다.
예) D가 (5, D)로 들어간 뒤, 더 짧은 (3,D)도 들어옴.
우선순위 큐: (3, D), (4, C), (5, D) ← 낡은 항목
(3, D)가 먼저 나와 D를 확정 → 나중에 (5, D)가 나오면 "이미 3으로 확정된 낡은 항목"이므로 무시.
전체 시간: O(V^2) → O((V+E) log V)
5) BFS와 다익스트라: 형제 알고리즘
공통점: 가까운 것부터 확정하고, 그 정점에서 이웃을 갱신.
※ 가중치가 전부 1이면, 다익스트라 = BFS. BFS가 확장되면 다익스트라인 것이다.
6) 음수 간선이 있으면, 확정이 번복된다.
B를 3으로 확정한 뒤, C(5)를 거쳐 음수 간선(-4)를 타면 5-4=1 < 3. 더 짧은 길이 나중에 등장.
확정이 번복되니 그리디가 깨지고 답이 틀린다.
음수 간선이 있을 땐 벨만-포드(더 느리지만 음수를 견딤).
그리고 다익스트라에 "목적지 방향 힌트"를 더하면 A* 알고리즘.
다익스트라는 끝이 아니라 더 강력한 알고리즘들의 출발점이다.
CS 돋보기
내비게이션 - 그 1초의 비밀
카카오맵, T맵, 구글맵 길찾기의 심장이 다익스트라(와 그 변형들)이다.
문제
: 전국 도로망은 정점이 수억 개. 날 것 그대로 돌리면 느림.
해법
: 지름길 미리 압축(전처리), 양쪽에서 동시에 탐색(양방향)
고급 최적화가 겹겹이 얹히지만, 본질적 사고는 변함없이 "확정하고 갱신한다".
"미리 계산해 둔다"는 누적합의 전처리 사고에, 양쪽에서 동시에 좁혀 오는 양방향 탐색까지 "겹겹이 얹혀진다".
인터넷 라우팅 - OSPF
OSPF(Open Shortest Path First) - 각 라우터가 네트워크 정보를 모아 다익스트라를 돌려 라우팅 테이블을 만든다.
BFS가 "최소 홉"이었다면, OSPF는 회선 속도, 지연을 가중치로 넣은 진짜 최단 경로이다.
다익스트라의 후예들
다익스트라(1956)
: A* (1969), 게임 길찾기 표준
: 벨만-포드, (음수 가중치 사용)
: Johnson's, 모든 쌍 최단
: CH, 대규모 내비
다익스트라는 게임, 내비, 라우팅, AI의 기본 도구가 되었다.
"비용이 다른 길에서 가장 효율적인 경로"가 보이면, 다익스트라를 권장.
실전에서는
게임
: RPG 자동 이동, RTS 부대 이동.
: 지형별 이동 비용 = 가중치
: Unity NavMesh 내부 길찾기
: 보스 추격 패턴
웹/서버
: OSPF, IS-IS 라우팅
: CDN 엣지 라우팅
: 차량 호출 매칭, 경로 안내
: 물류 배송 최적화
일반 CS
: 회로 설계의 신호 경로
: 그래프 신경망(GNN)
: 유전자, 단백질 네트워크
: 네트워크 플로우의 부품
※ "가까운 것부터 확정한다"는 사고는, 컴퓨터 과학 곳곳의 토대이다.
오늘의 핵심
다익스트라
: 가중치 그래프의 최단 경로
: BFS의 가중치 일반화(비용이 다 같으면 BFS와 동치)
확정과 갱신
: 미확정 중 거리 최소를 확정 → 그 정점에서 이웃을 갱신 → 전부 확정될 때까지 반복.
그리디를 활용
: "지금 가장 가까운 정점은 이미 최단"
: 단, 음수 간선이 없을 때 성립.
우선순위 큐가 핵심 도구
: 큐 → BFS의 큐 → 우선순위 큐로 진화. O((V+E) log V)
확장의 출발점
: 음수 간선은 벨만-포드, 방향 힌트를 더하면 A*.
댓글
댓글 쓰기