다익스트라 알고리즘1

• 

  다익스트라 알고리즘 데이크르스라 알고리즘 Dijkstra Algorithm 일명 다익스트라 알고리즘이라고도 한다. - 보통 음의 가중치가 없는 가주치 방향 그래프를 기준으로 최소 비용으로 노드를 방문하거나 노드를 이어가는 문제들에 많이 쓰인다 => 가중치 방향 그래프란 노드에서 다른 노드로 갈 때 일정한 비용이 드는 그래프를 의미한다. - 기본적으로 O(V^2) 의 시간복잡도를 가지나 PriorityQueue 나 sort 를 사용해서 O(VlogV) 의 시간 복잡도를 만들어서 계산하게 된다. 다익스트라 알고리즘 코드 보통 아래와 같은 순서로 코드 작성한다. 0. 정점과 비용을 위한 Edge class 를 만들어둔다 1. n번째 노드에서의 최소 cost 로 방문할 수 있는 도로를 찾기위해 PriorityQueue 를 사용한다.. Java - 알고리즘 2022. 8. 27.