목록다익스트라 (1)
Typing diary
다익스트라(Dijkstra) 알고리즘
다익스트라 DP에 기반한 최단 경로 탐색 알고리즘 알고리즘 수행 결과로 최단 경로트리를 반환한다. 아이디어 힙 자료구조를 이용하여 출발 노드에서 부터 해당 노드까지 비용이 적은 순으로 경로를 탐색한다. 다음과 같은 그래프가 있다고 하자. 다익스트라 알고리즘으로 해당 그래프를 탐색하게 되면 출발 노드부터 해당 노드까지 비용이 적은순 (1 → 4 → 2 → 5 → 3 → 6)으로 탐색을 하게 된다. 해당 과정을 구현하기 위해선 현재 탐색 가능한 노드 중 비용이 가장 적은 노드가 무엇인지 알아야 한다. (이때, 현재 탐색 가능한 노드란, 방문 했던 노드와 인접한 노드를 뜻한다.) 이를 위해 힙 자료구조를 사용하게 된다. . 이게 무슨 소리냐... 1번 노드를 시작 노드로, 6번 노드를 도착 노드로 정하자. 1..
알고리즘
2022. 10. 31. 16:57