최단 경로 문제란 ?우리가 길을 찾을 때 가장 빠른 길을 고민하듯이, 컴퓨터 과학에도 비슷한 문제가 있다. 바로 최단 경로 문제(Shortest Path Problem)이다. 이 문제는 가중 그래프에서 한 정점(시작점)에서 다른 정점(도착점)까지 가는 경로 중 가중치의 합이 최소가 되는 경로를 찾는 것을 목표로 한다. 여기서 가중치는 간선(edge)에 붙은 숫자로, 거리, 시간, 비용 등을 나타낼 수 있다.예를 들어, 도시 A에서 도시 C로 가는 길이 두 개 있다고 해보자. 하나는 직진해서 10km이고, 다른 하나는 B를 거쳐서 7km라면, 당연히 7km인 경로를 선택할 것이다. 최단 경로 문제는 이런 상황을 수학적으로 해결하는 방법이다. 이번 포스팅에서는 이 문제를 효율적으로 푸는 방법 중 하나인 다익..
