목록다익스트라 알고리즘 (1)

JINWOOJUNG

[ DP ] Dijkstra Algorithm

금일은 다익스트라 알고리즘에 대하여 자세히 알아보자. 다익스트라 알고리즘은 Dynamic Programming을 활용한 최단 경로 탐색 알고리즘이다. 다익스트라를 DP를 활용하여 접근할 수 있는 이유는 최단 경로는 각각의 최단 경로를 포함하고 있기 때문이다. 따라서 이전까지 계산해 둔 최단 경로를 사용하여 하나의 최단 거리를 구한다. 기본적은 다익스트라 알고리즘의 프로세스는 다음과 같다. 1. 출발 노드 설정 2. 출발 노드를 기준으로 각 노드의 최소 비용 저장3. 방문하지 않은 노드 중 최소 비용 노드 설정4. 해당 노드를 경유해서 특정한 노드로 가는 경우를 고려해 최소 비용 갱신5. 2~4번 과정 반복  위와 같은 그래프가 주어졌다고 하자. 각 노드사이로 연결 된 간선은 비용을 의미한다. 각 문제에 ..
백준 2024. 5. 25. 15:03
이전 Prev 1 Next 다음