반응형
Dijkstra
-
[알고리즘] Dijkstra 알고리즘알고리즘 2021. 12. 4. 03:02
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. Dijkstra 알고리즘이란? 음의 가중치(비용)이 없는 그래프에서 특정 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘을 말합니다. 다익스트라 알고리즘은 그리디와 다이나믹 프로그래밍 방법을 사용하여 구현합니다. 다익스트라는 시작 노드에서 아직 방문하지 않은 노드들 중 최단거리 노드를 선택 합니다. (그리디 기법) 다익스트라는 시작 노드에서 갈 수 있는 노드들을 방문하면서 비용이 최소면 갱신합니다. (다이나믹 프로그래밍 기법) 위 2가지 방법을 반복하여 특정 노드에서 나머지 모든 노드로 가는 최단거리를 구하는 알고리즘 입니다. 2. 알고리즘 방법 그래..