728x90 반응형 다익스트라1 다익스트라 알고리즘 다익스트라 알고리즘(Dijkstra 알고리즘) 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다. 다익스트라 알고리즘의 경우 어떤 경우에는 다이나믹 프로그래밍, 어떤 경우에는 탐욕 알고리즘으로 분류되기도 한다. 탐욕 알고리즘이란? 현재 상황에서 여러가지 경우가 있을 경우, 그 순간의 최선의 선택을 하는 알고리즘이다. 작동 과정 출발 노드를 설정 출발 노드를 기준으로 각 노드의 최소 비용을 저장 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 위 과정에서 3~4.. 2019. 4. 23. 이전 1 다음 728x90 반응형