지도에서 두 지점 간의 가장 짧은 경로를 찾는 방법은 다음과 같다.그래프에 방향과 가중치가 표현되어있다고 했을 때, 경로 p는 시작점에서 끝점으로 이어지는 정점의 순서가 된다.w(p)는 경로 p에 포함된 간선들의 가중치 합이 된다. 이 w(p)가 최소일 때, 가장 짧은 경로라고 한다. 그래프에서 노드v에서 노드 u로 갈 수 없는 경우에는, 무한대로 표현한다. 최단 경로는 여러 개가 존재할 수 있으며, 한 노드에서 다른 모든 노드로 가는 최단 경로들은 트리 형태로 구성된다.가중치는 경로를 따라 누적되며, 우리가 최소화해야하는 값으로 해석된다. 최단 경로 문제에는 몇가지 유형이 존재한다.Single-source (단일 출발점): 주어진 출발점 s에서 그래프의 모든 정점 v까지의 최단 경로를 찾는 문제Sin..
