728x90
📗 다익스트라 알고리즘
DP를 활용한 대표적인 최단 경로 탐색 알고리즘이다.
특정 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.
✔ 왜 DP 문제?
다익스트라 알고리즘이 DP 문제인 이유는
"최단 거리는 여러 최단 거리로 이루어져있기 때문이다"
따라서 작은 문제가 큰 문제의 부분집합에 속해 있다고 볼 수 있다.
기본적으로 다익스트라는
"하나의 최단거리를 구할 때 그 이전까지 구했던 최단거리 정보를 그대로 사용한다"는 특징이 있다.
현재까지 알고있던 최단 경로를 계속해서 갱신해나간다.
📗 다익스트라 매커니즘
기본적으로 DP와 그리디 기법을 사용한다.
아래 두 단계를 반복해 임의의 노드에서 각 모든 노드까지 최단거리를 구한다.
1. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. (그리디)
2. 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. (DP)
다익스트라 알고리즘의 대표 문제인 '최단 경로' 문제를 풀어보았다.
https://daneng4-codingstory.tistory.com/66
728x90
반응형
'알고리즘' 카테고리의 다른 글
에라토스테네스의 체 - seive of eratosthenes (0) | 2024.02.23 |
---|---|
이분 탐색 - Binary Search (0) | 2023.11.11 |
그래프 탐색 - DFS & BFS (0) | 2023.10.27 |
삽입 정렬 - Insertion Sort (0) | 2023.10.18 |
선택 정렬 - Selection Sort (0) | 2023.10.17 |