Dijkstra1 [Algorithm] 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘이며 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 두 노드 간의 최단경로를 찾는 알고리즘이기도 하다. (무방향/ 방향그래프 둘다 상관없이 사용가능하다) 해당 알고리즘은 DP(다이나믹 프로그래밍)와 Greedy Algorithm(탐욕 알고리즘)을 복합적으로 사용하는 알고리즘이다. 최단거리는 여러개의 최단거리로 나눠져있고 이전까지 구한 최단 거리는 그대로 사용한다 → DP 눈앞에 보이는 최적의 선택을 한다 → Greedy 예시를 들면서 한번 다익스트라로 어떻게 풀어나가는지 확인해보고 마무리 지어보겠습니다. 예시 네비게이션 1번에서 6번을 최단 경로로 찾아가야하는 상황에서 모든 노드까지의 최단거리.. 2024. 4. 8. 이전 1 다음 728x90
