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

Dijkstra Algorithm

• 가중치가 있는 그래프의 최단 경로를 구하는 문제는 대부분 이 알고리즘을 사용
• 각 단계에서 가장 좋은 것을 선택하는 전략을 가진 Greedy 알고리즘과 원리가 같음. but dijkstra 알고리즘은 한 번 방문한 노드는 다시 방문하지 않음 -> 음의 가중치가 있는 그래프에서는 제대로 동작하지 않음

1. 시작 노드를 설정하고 시작 노드로부터 특정 노드까지의 최소 비용을 저장할 공간과 직전 노드를 저장할 공간 마련
   1-1. 최소 비용과 직전 노드를 저장할 공간은 매우 큰 값으로 초기화
   1-2. 시작 노드의 최소 비용은 0, 직전 노드는 자신으로 설정
2. 해당 노드를 통해 방문할 수 있는 노드 중(아직 방문하지 않은 노드 중) 현재까지 구한 최소 비용이 가장 적은 노드 선택
   2-1. 해당 노드를 거쳐서 각 노드까지 가는 최소 비용과 현재까지 구한 최소 비용을 비교하여 작은 값을 각 노드의 최소 비용으로 갱신
   2-2. 이 때 직전 노드도 같이 갱신
3. 노드 개수에서 1을 뺀 만큼 반복