다익스트라 알고리즘 정리, 최단 경로를 한 단계씩 따라가 보고 음수 가중치에서 틀리는 이유까지

내비게이션이 가장 빠른 길을 찾고, 라우터가 패킷을 보낼 경로를 정할 때 바탕에 있는 생각은 같습니다. 출발점에서 가까운 곳부터 확정해 나가는 것입니다. 다익스트라 알고리즘은 정보처리기사 알고리즘 문제와 네트워크 과목의 OSPF(링크 상태 라우팅)에 동시에 걸쳐 있는 토픽입니다.

다익스트라는 가장 가까운 미확정 정점부터 거리를 확정하는 탐욕 알고리즘

정의: 가중치가 0 이상인 그래프에서 한 출발 정점으로부터 모든 정점까지의 최단 거리를 구하는 알고리즘으로, 아직 확정되지 않은 정점 중 거리가 가장 작은 정점을 골라 확정하고 그 이웃의 거리를 갱신(완화, Relaxation)하는 과정을 반복합니다(Dijkstra, 1959).

• 핵심 키워드: 단일 출발점 최단 경로, 탐욕법, 완화(Relaxation), 우선순위 큐
• 완화: dist[u] + w(u,v) < dist[v] 이면 dist[v]를 더 짧은 값으로 바꾸고 직전 정점을 u로 기록합니다.

예시 그래프로 따라가는 단계별 거리 갱신

단계	확정 정점	S	A	B	C	D
초기	–	0	∞	∞	∞	∞
1	S(0)	0	4	1	∞	∞
2	B(1)	0	3 (B 경유)	1	6	∞
3	A(3)	0	3	1	4 (A 경유)	8
4	C(4)	0	3	1	4	7 (C 경유)
5	D(7)	0	3	1	4	7

S에서 A로 바로 가면 4지만, B를 거치면 1+2=3으로 더 짧습니다. 최종 D까지의 최단 경로는 S → B → A → C → D, 거리 7입니다. 직전 정점 기록을 거꾸로 따라가면 경로가 복원됩니다. 위 결과는 코드로 검산했습니다.

시간 복잡도는 구현 자료구조가 좌우한다

구현	최솟값 찾기	전체 복잡도	유리한 경우
배열(선형 탐색)	O(V)	O(V²)	간선이 많은 밀집 그래프
이진 힙 우선순위 큐	O(log V)	O((V+E) log V)	간선이 적은 희소 그래프

음수 가중치가 있으면 왜 틀리는가

다익스트라는 한 번 확정한 거리는 다시 줄어들지 않는다고 가정합니다. 가중치가 모두 0 이상이면 나중에 찾은 경로는 항상 더 길거나 같기 때문에 이 가정이 성립합니다. 음수 간선이 있으면 이미 확정한 정점으로 돌아오는 더 짧은 경로가 생길 수 있어 결과가 틀립니다. 이때는 벨만-포드를 씁니다.

알고리즘	문제 유형	음수 가중치	복잡도
다익스트라	단일 출발점	불가	O((V+E) log V)
벨만-포드	단일 출발점	가능, 음수 사이클 탐지	O(VE)
플로이드-워셜	모든 쌍	가능(음수 사이클 없을 때)	O(V³)

답안에서 놓치기 쉬운 포인트

• 최소 신장 트리(크루스칼·프림)와 혼동하지 마세요. 다익스트라는 출발점 기준 경로 길이를, MST는 전체 연결 비용을 최소화합니다.
• 네트워크 과목 연결: OSPF는 각 라우터가 링크 상태 정보로 다익스트라(SPF)를 계산해 라우팅 테이블을 만듭니다. 거리 벡터 방식인 RIP와 대비해 쓰면 좋습니다.
• 목적지가 하나뿐이면 휴리스틱을 더한 A* 알고리즘이 탐색량을 줄입니다.

시험 직전 한 줄 요약

다익스트라는 비음수 가중치 그래프에서 가장 가까운 미확정 정점을 확정하고 이웃을 완화하는 탐욕 알고리즘으로, 힙 사용 시 O((V+E) log V)이며 음수 간선이 있으면 벨만-포드를 씁니다.

학습용 정리이며 실제 시험 문항과 다를 수 있습니다. 출제 기준은 큐넷 공지를 확인하세요. 그림은 이해를 돕기 위한 개념도와 예시입니다.