1. 다익스트라 알고리즘
다익스트라 알고리즘을 순서대로 나타내면 다음과 같습니다.
단순한 최단경로 찾기는 위와 같이 풀 수 있습니다.
하지만 최단경로 상의 모든 정점을 찾고 싶을 때는 위의 과정 중에 추가적인 알고리즘이 필요합니다.
2. 다익스트라 알고리즘으로 최단경로의 정점 찾기
우선순위 큐에 다음 정점에 대한 정보를 추가할 때, 가중치를 더 작은 값으로 하는 간선 정보를 저장합니다.
최단경로 탐색이 종료되면, 간선 정보를 담은 표를 가지고 역으로 거슬러 올라가며 최단경로 상의 모든 정점을 순서대로 확인할 수 있습니다.
