벨만 방정식 · 제6회

가장 빠른 길내비게이션은 수백만 갈래 길에서 어떻게 최단 경로를 찾을까?

벨만방정식방의 마지막 — 다익스트라 알고리즘이에요. 벨만의 ‘최적성 원리’를 그래프에 적용해, 출발점에서 가까운 곳부터 차근차근 최단 거리를 확정해 나가요. 내비게이션·라우팅의 심장이죠.

01모든 길을 다 볼 순 없다

도시의 교차로와 도로가 그물처럼 얽혀 있어요. 출발지 S에서 목적지 T까지 가장 짧은(빠른) 길을 어떻게 찾을까요? 모든 경로를 세면 폭발해요.

비결 — 이미 확정된 최단거리에서 한 걸음씩 확장(가장 가까운 미확정 지점을 확정). 벨만의 최적성 원리예요.

02직접 해보기 — 최단 경로 찾기

숫자는 도로의 거리(비용)예요. 최단경로 찾기를 누르면 각 교차로까지의 최단거리가 확정되고, S→T 최단 경로가 파랗게 빛나요.

S→T 최단 거리 = —
‘최단경로 찾기’를 눌러 보세요.

다익스트라는 확정된 최단거리를 절대 다시 안 고쳐요 — 가까운 순서로 하나씩 확정하니까요. 그래서 빠르죠. 동적계획법처럼 부분 최적을 쌓아 전체 최적을 만드는 벨만의 지혜예요.

03가까운 곳부터 확정

dist(v) = min이웃 u [ dist(u) + 거리(u,v) ]

각 지점의 최단거리는 이웃의 최단거리 + 그 도로 거리 중 최소예요(벨만 방정식의 그래프판). 가장 가까운 미확정 지점을 탐욕적으로 확정하며 퍼져요. 내비게이션·인터넷 라우팅·지도·게임 AI가 이걸 써요.

04스스로 점검하기

점수 0 / 0

05더 깊이 — 세 개의 수심

고교가중그래프·최단경로 직관도로 거리, 가까운 곳부터 확정, 최적성 원리.
학부다익스트라·벨만–포드·A*우선순위큐 구현, 음의 가중치(벨만–포드), 휴리스틱 A*.
대학원대규모 경로·근사·강화학습도로망 전처리(CH), 실시간 라우팅, 최적제어·RL과의 연결.

벨만 6부작 완주! — 가치반복부터 다익스트라까지, 최적 결정의 수학을 훑었어요. 궁금한 건 방의 Q&A 봇에! 🎉

『수요를 따라가는 수학 · 벨만 방정식』 제6회. 다익스트라 최단경로 시뮬레이터 + 자동채점. · 벨만방정식방으로