🔻다익스트라 알고리즘(Dijikstra's Algorithm) 다익스트라 알고리즘이란 가중치 그래프에서 한 정점으로부터 모든 정점의 최단거리를 구하는 알고리즘이다. 다익스트라의 경우 가중치에 음수가 존재하면 안된다는 제약사항이 존재한다. 🔶다익스트라 알고리즘의 원리 다익스트라 알고리즘의 기본적인 원리는 굉장히 간단하다. 두가지 작업을 모든 정점을 모두 방문할 때까지 반복하는 것이다. 1. 방문하지 않은 정점 중 가장 cost가 작은 정점을 방문한다. 2. 해당 정점과 연결된 정정들 중에서 거리가 이전에 기록한 값보다 작다면 값을 갱신한다 이 두작업을 무한 반복하는 것인데, 글로만 보면 무슨 말인지 이해하기 힘들 수 있으니 그림을 통해 알아보자. 6개의 정점이 있고 각 정점사이의 cost가 그림과 같은 그..