greedy algorithm1 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra)란?다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘 입니다. 즉 하나의 정점에서 모든 정점으로 가는 최단 경로를 알려준다. -> ex) 인공위성다만 음의 간선을 포함할 수 없으며, 현실에도 음의 간선은 존재하지 않기에 현실에서 사용하기 적합한 알고리즘 입니다. 예제1)"1부터 다른 노드로 가는 최단 경로를 구해보자"1. 1의 연결 노드는 2, 3, 4이며 각각 3, 6, 7로 산정할 수 있다.0367위 그래프는 1, 2, 3, 4 다른 노드로 가는 비용을 정리한 것 2. 그럼 비용이 가장 저렴한 2번 노드로 가서 산정을 해본다. 이때 무한은 접근 할수가 없는 노드이다.301무한이렇게 되면 3번 노드는 3 + 1로 이전에 있었던 6비용보다.. 2024. 5. 1. 이전 1 다음
