반응형 알고리즘/탐색1 [알고리즘] 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 방향/무방향 그래프에서 하나의 시작점에서 모든 정점까지의 최단 거리를 구해주는 알고리즘입니다. 주의할 사항은 방향/무방향 그래프에서 간선의 가중치가 양수여야만 합니다. 음수인 경우 시작점에서 거리가 가까운 정점을 구하고 탐색을 이어나가다가 음수 간선을 마주치면 거리가 줄어들 수 있어서 알고리즘이 불완전하게 됩니다. 다익스트라는 다이내믹 프로그래밍(Dynamic Programming)을 적용한 탐색 알고리즘이기도 합니다. 예를 들어 A에서 F까지 가는 최단 거리의 경로가 A → B → C → D → E → F 라고 합시다. 그럼 이 경로에 포함되어있는 모든 부분 경로는 최단 거리입니다. A부터 E까지의 최단 거리 경로인 A → B → C → D →.. 2021. 5. 14. 이전 1 다음 반응형
