[알고리즘] 다익스트라 (Dijkstra)

다익스트라 알고리즘 개념

다익스트라(dijkstra) 알고리즘은 음수 가중치가 없는 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 탐색하는 알고리즘이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

다익스트라 알고리즘 과정

1. 모든 정점의 거리 값을 무한대로 초기화한다.