다익스트라

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

다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍(DP)과 그리디 알고리즘을 활용한 최단경로 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 알 수 있으며, 간선의 가중치가 양수일 때 사용가능하다. 다익스트라 알고리즘이 DP라고 할 수 있는 이유는 특정 최단 거리는 여러 개의 최단거리로 이루어져 있기 때문이며, 하나의 최단 거리를 구할 때 특정 정점까지의 최단거리 정보를 그대로 가져와 사용하기 때문이다. 또한 그리디 알고리즘이라고 말할 수 있는 이유는 특정 최단 거리에 최단 거리를 더해가며 최종적인 최단거리를 계산하는 방식이기 때문이다. (다익스트라 알고리즘을 공부한 뒤 다시 읽으면 쉽게 이해가능) 한 정점에서 다른 모든 정점까지의 최단거리를..