면접 대비 프로그래밍 지식/알고리즘1 [알고리즘]다익스트라 알고리즘 다익스트라 알고리즘은 최단 경로를 알기위한 알고리즘입니다. 즉 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. 그러나 해당 알고리즘은 음의 간선을 포함할 수 없으므로 이를 유의해야 합니다. 또한 이를 구현하는 방법에 힙 자료구조를 이용하는 방법이 있어, 자바를 이용해 구현하는 본 게시글에서는 PriortyQueue 클래스를 활용하여 구현하는 코드를 포함합니다. 다음은 예제입니다. 다익스트라의 진행 순서는 다음과 같습니다. 1. 시작점을 선택 2. 이동이 가능한 노드 중 가장 거리가 짧은 노드를 선택 3. 현재 구해진 각 노드까지의 거리와 선택된 노드를 거쳐 각 노드를 방문하는 거리를 비교 -> 선택된 노드를 거쳐 해당 노드를 방문하는 거리가 더 짧은 경우 거리를 갱신 4. 2번과.. 2021. 4. 13. 이전 1 다음
