Dijkstra는 대표적인 길찾기 알고리즘입니다. Dijkstra 알고리즘을 이용하여 출발 노드에서 종말 노드로 가는 최단 거리(최소 비용)의 경로를 찾을 수 있습니다. 아래와 같은 그래프를 생각해봅시다. 그래프 B에서 출발해 E에 도착하는 경로는 여러개가 있습니다. 여러개의 경로 중에서 최소 비용을 가지는 경로가 우리가 원하는 경로가 될것입니다. 노드에서 노드 사이를 옮겨다닐때 비용이 발생한다고 하면 경로의 비용은 $Cost(path) = \sum\limits_{i=1}^n Cost(edge),\text{ }(edge_1,edge_2...edge_n은\text{ }path에\text{ }속함)$이 됩니다. $edge$가 노드와 노드를 연결하니 $edge$에 비용을 추가하면 아래와 같이 됩니다. cost 추가 그럼 이제 경로를 구성하는 $edge$를 구하면 됩니다. 방문한 노드들을 트리 형식으로 구축하여 경로를 구성하는 $edge$들을 구할 수 있습니다. B-E 경로들 B에서 출발해 E에 도달하는 총 6개의 경로를 구할 수 있습니다. (주의: 진행 중인 경로에 속한 노드를 재방문할 수 없습니다. 그렇지 않으면 무한루프에 빠지게 됩니다.) 경로들에 대한 비용을 계산해 보면, $\begin{eqnarray} B\to A\to D\to C\to E &= 9 \\ B\to A\to D\to E &= 6 \\ B\to D\to C\to E &= 10 \\ B\to D\to E &= 7 \\ B\to C\to D\to E &= 5 \\ B\to C\to E &= 6 \end{eqnarray}$ $B\to C \to D \to E$가 최소 비용 거리임을 확인 할 수 있습니다. 최소 비용 거리 $Cost(edge)$를 거리로 두면 최단 거리, 시간으로 두면 최소 시간의...