dijkstra1

• 

  다익스트라(dijkstra) 알고리즘 (+Java 코드) 1. 다익스트라란? 다익스트라 알고리즘은 최단 거리를 구하는 알고리즘입니다. (1) 조건 다익스트라 알고리즘을 사용하여 문제를 풀기 위해서는 조건이 있습니다. 음수 가중치가 없어야 한다. 음수 가중치가 있는 그래프에서 최단 거리를 구하기 위해서는 벨만-포드 알고리즘을 사용하면 됩니다! 2. 다익스트라 알고리즘 방식 그렇다면 어떻게 그래프의 최단 거리를 구하는걸까요? 아직 방문하지 않은 정점 중 출발지로부터 가장 가까운 정점을 방문합니다. -> 우선순위 큐 해당 정점을 거쳐 갈 수 있는 정점의 거리가 이전 기록한 값보다 작으면 갱신합니다. (1)번 과정에서 출발지로부터 가장 가까운 정점을 방문해야 하기 때문에 구현할 때에는 우선순위 큐를 사용합니다. 예시를 통해 알아봅시다. (0) 예시 그래프 (1) 출발.. Algorithm & Data Structure/이론 2024. 4. 18.