다익스트라 알고리즘개요 그래프에서 단일 시작 최단 경로 문제는 시작 정점과 목적 정점이 주어졌을 때, 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 찾는 문제다. 이 문제를 해결하는 여러 알고리즘 중 하나가 다익스트라 알고리즘(Dijkstra's algorithm)이다. 다익스트라 알고리즘은 음수 가중치를 갖지 않는 그래프에서 사용되는 최단 경로 탐색 알고리즘이다. 이 알고리즘은 프림의 최소 신장 트리(MST) 알고리즘을 변형한 것으로, 다음과 같은 절차를 따른다. 시작 노드를 설정시작 노드의 거리 값은 0으로, 이를 제외한 모든 노드의 거리 값은 무한대로 초기화모든 거리 값을 최소 힙에 추가최소 힙으로부터 꺼낸 정점 U와 인접한 모든 정점 V에 대해, 만약 V의 거리 값이 (U의 거리 값 +..
