다익스트라 알고리즘(Dijkstra's Algorithm) 자세하게 이해하기
다익스트라 알고리즘(Dijkstra's Algorithm)은 간선(edge)의 가중치가 있는 그래프에서 시작점이 고정되어 있을 때 모든 정점(vertex, 복수형은 vertices)으로 가는 최단 경로의 거리 합을 모두 구하는 알고리즘으로 에드거 다익스트라(Edsger Dijkstra) 가 1959년에 발표했다. 알고리즘을 설명하기 앞서 몇가지 기호들을 정의하고 시작한다. : Permanent Label 라는 의미로, 확실하게 최단거리 계산이 끝난 정점들이 들어가는 집합이다. : Temporary Label 라는 의미로, 집합 PL에 포함된 정점을 거쳐 갈 수 있는 최단거리가 계산된 정점의 집합이다. : 시작점에서 정점 까지 도달하기 위한 확실한 최소 거리로써 ..
