목록다익스트라최단경로 (1)

INEEDACHACHA

Dijkstra (다익스트라 - 최단거리 알고리즘)

개념 다익스트라(dijkstra) 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. "특정" 노드에서 다른 "모든" 노드로 가는 최단경로를 계산한다. 양의 가중치에서 사용한다. 매 상황(현재 노드에서 다른 노드로 이동)때 가장 비용이 적은 노드를 선택한다(그리디) 현재 최소거리 Distance Table을 갱신하면서, dp 유형에도 해당하는 알고리즘이다. 예시 하기와 같은 무방향 그래프가 주어졌다고 가정하자. 출발점 A로 시작한다고 가정하면, 갈 수 있는 곳은 B,D 두 군데이며, 시작점(A)에서 가까운 B로 간다. B로 이동 후, 갈 수 있는 곳은 E,D 두 군데이며, 테이블을 갱신 후, 시작점(A)에서 가까운 D로 간다. D로 이동 후, 갈 수 있는 곳은..
Algorithm/Basic 2024. 3. 15. 19:39
이전 Prev 1 Next 다음