데이크스트라 알고리즘은 프림 알고리즘과 매우 유사합니다. 탐욕 알고리즘에 기반하고 있습니다. 데이크스트라 알고리즘의 가장 중요한 특징은 그래프에 음수 가중치를 인정하지 않는다는 것입니다.

데이크스트라 알고리즘을 구현하려면 S라는 집합과 distance라는 배열이 필요합니다. 집합 S는 최단 경로가 발견된 정점 집합으로, 최단 경로를 찾고 있는 그래프 G의 정접 집합 V(G)와 같아질 때까지 커집니다. 또 어떤 정점 v를 인덱스로 하는 distance[v] 값은 출발 정점에서 집합 S에 있는 정점만 거쳐 목적지 v에 도달하는 경로 길이입니다. 점점 커지는 집합 S와 계속 변경되는 최단 경로 distance는 어딘가 낯이 익습니다. 눈치챘나요? 프림 알고리즘에서 자라나는 최소 비용 신장 트리의 정점 집합 TV와 가장 낮은 가중치를 저장해 놓은 w_list가 자연스럽게 떠오르는군요. 맞습니다. 집합과 배열 의미는 다르지만 구현이 매우 비슷해질 것임을 추측할 수 있습니다. 그것은 다음 절에서 좀 더 살펴보도록 하죠.

데이크스트라 알고리즘에서 중요한 연산은 relax입니다. 먼저 이 연산을 알아보겠습니다.