Always Be Wise

다익스트라 알고리즘(Dijkstra Algorithm)은 그래프 내 하나의 정점에서 다른 모든 정점까지의 최단 거리/경로를 구하는 알고리즘이다. BFS와 다른 점은 가중치 그래프에서도 사용 가능하다는 것이다. 다만, 그래프 내 엣지들은 모두 양수여야 한다. 다익스트라 알고리즘의 기본 동작 원리는 다음과 같다. 1. 출발 정점을 설정한다. 2. 최단 거리 테이블을 초기화한다. 이때, 초기 값은 출발 정점을 제외하고 모두 무한대 값을 가진다. 3. 출발 정점과 연결된 정점 가운데 방문하지 않는 정점들을 찾는다. 4. 그중 최단 거리가 가장 짧은 정점을선택한다. 이때, 최단 거리란 갱신하기 전 최단 거리를 의미하며 2번에서 초기화한 테이블의 값과는 다르다. 5. 해당 정점을 거쳐 다른 정점으로 가는 거리를 ..