G·Graph Daily Lab
DAY 13 / 100
내 학습 기록
DAY 13개념·실험탐색과 경로

가중치가 있는 최단 경로

엣지마다 걸리는 시간이 다르면 홉 수로는 최단 경로를 찾을 수 없습니다. 가장 확실한 노드부터 하나씩 확정해 나가는 방법을 배웁니다.

약 20분조작형 실험 확인 퀴즈
A SMALL DETOUR

이번 회차, 내 속도로.

기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 13로 돌아옵니다.

난이도·관심 주제 고르기
이번 회차는 어느 속도로 볼까요?
더 살펴볼 주제 1~2개 선택

1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.

이렇게 다녀와요 1단계 · 약 12분

  1. 출발 · DAY 13다익스트라·완화
  2. 1. 관심 주제FIFO·LIFO·방문 표시추가 05 · 새 추가 수업
  3. 복귀 · DAY 13원래 회차 이어가기
  • FIFO·LIFO·방문 표시 · 11·12회차에서 큐와 스택의 상태 변화가 헷갈렸다면, 작은 나무 모양 그래프로 한 줄씩 따라가 봅니다.

선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.

복귀: DAY 13 → 본과정 다음 회차: DAY 14
01 / UNDERSTAND

핵심 개념

다익스트라(Dijkstra, 1959)는 가중치가 음수가 아닌 그래프에서 한 출발 노드로부터 다른 노드까지의 최단 경로를 구하는 방법을 발표했습니다. 같은 논문은 모든 노드를 가장 짧은 총길이로 잇는 문제(최소 신장 트리)도 함께 다룹니다. 아이디어는 BFS의 ‘층’ 대신 ‘지금까지 알려진 거리’를 기준으로 가까운 노드부터 확정하는 것입니다.

출발 노드의 거리를 0, 나머지를 ∞(아직 모름)로 둡니다. ① 확정되지 않은 노드 중 현재 거리가 가장 작은 노드를 확정합니다. ② 그 노드에서 나가는 엣지마다 ‘확정한 노드의 거리+엣지 가중치’가 이웃의 현재 거리보다 작으면 값을 바꾸고 이전 노드를 기록합니다. 이 갱신을 완화(relaxation)라고 합니다. ③ 모든 노드를 확정할 때까지 반복합니다. 도착 노드에서 이전 노드를 거꾸로 따라가면 경로가 나옵니다.

한번 확정한 거리가 뒤집히지 않는 이유는 가중치가 음수가 아니기 때문입니다. 지금 가장 작은 거리의 노드에 더 짧게 닿으려면 그보다 먼 노드를 거쳐 와야 하는데, 엣지를 더할수록 비용이 줄지 않으니 불가능합니다. 음수 가중치가 있으면 이 논리가 깨지므로 벨만–포드(Bellman–Ford) 같은 다른 방법을 씁니다. 모든 가중치가 1이면 다익스트라는 BFS와 같은 거리를 냅니다.

다익스트라는 거리가 가장 작은 미확정 노드를 확정하고 이웃을 완화하는 일을 반복해, 음수가 없는 가중 그래프의 최단 경로를 찾습니다.
02 / WORKED EXAMPLE∑

작은 예제로 따라가기

01

가중치(분)가 S–A 4, S–B 1, B–A 2, A–T 3, B–C 4, C–T 2입니다. S를 0으로 확정하고 이웃을 완화해 A=4, B=1을 적습니다.

02

가장 작은 B(1)를 확정하면 A는 1+2=3으로 줄고(이전 노드 B) C=1+4=5가 됩니다. 다음으로 A(3)를 확정해 T=3+3=6을 적습니다.

03

C(5)를 확정해도 5+2=7은 6보다 커서 T는 그대로입니다. T(6)를 확정한 뒤 이전 노드를 거꾸로 따라가면 S→B→A→T, 3홉·6분입니다. 2홉인 S→A→T는 7분입니다.

03 / EXPLORE

직접 실험해 보기

‘다음 확정’을 누르기 전에 어느 노드가 확정될지 먼저 예측하고, 표에서 현재 거리와 이전 노드가 완화로 바뀌는 순간을 확인한 뒤 마지막에 강조되는 S→T 경로의 홉 수와 비용을 적으세요.

LIVE EXPERIMENT · DIJKSTRA

가장 가까운 역부터 확정하기

표에서 미확정 역 중 거리가 가장 작은 역이 다음에 확정됩니다. 누르기 전에 먼저 예측해 보세요.
25163135S0A∞B∞C∞D∞T∞
방금 확정·완화확정거리 있음, 미확정
0개 확정S의 거리를 0, 나머지를 ∞로 두고 시작합니다.
역거리이전상태
S0–미확정
A∞–미확정
B∞–미확정
C∞–미확정
D∞–미확정
T∞–미확정
확정 0/6 · 이번 완화 0건 · 소요 시간은 학습용 가상 값
04 / RECALL & PRACTICE

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

문제 1
힌트 보기

X(2)를 확정하면 Y가 5에서 2+1=3으로 줄어듭니다.

풀이와 비교하기

확정 순서는 S(0), X(2), Y(3), Z(5)입니다. X를 확정할 때 Y=3, Z=8이 되고, Y를 확정할 때 Z가 3+2=5로 줄어듭니다. 최단 경로는 S→X→Y→Z, 비용은 5입니다.

풀이와 확인 표시는 이 브라우저에 저장됩니다.

YOUR NOTES

오늘 이해한 것과 다시 볼 것

계산이 달라진 이유, 헷갈린 개념, 다음에 확인할 질문을 남겨 보세요.

메모는 이 브라우저에 저장됩니다. 홈에서 전체 기록을 내려받을 수 있습니다.
05 / CHECK YOURSELF

오늘의 이해 확인

다익스트라 알고리즘이 다음에 확정할 노드를 고르는 기준은?

완료 조건: 확인 퀴즈 정답 · / 직접 풀기 0/1

FURTHER READING

더 깊이 읽기

예제와 실험 데이터는 이 과정을 위해 만든 것입니다. 원문은 선택 자료이며, 강의와 직접 풀기만으로도 다음 회차를 이어갈 수 있습니다.

A note on two problems in connexion with graphsDijkstra (1959)

이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.