다익스트라(dijkstra) 알고리즘 다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘이다. 가중치 그래프 상에서 출발노드에서 목표노드까지 이동하는 가장 짧은 경로를 찾는 방법을 찾는다. 하나의 출발 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있다. 에지(간선)은 모두 양수여야 한다. 시간 복잡도 : O(ElogV) 그리디와 DP의 특성을 갖고 있다. 다익스트라 알고리즘 동작 원리 1. 인접 리스트로 그래프를 구현한다. [1] ->[ 2, 8 ] 은 1에서 2로 가는 가중치가 8이라는 뜻이다. 실제로는 아래와 같이 Edge 클래스를 만들어서 Edge 형 ArrayList배열을 선언하여 구성하였다. ArrayList[] graph; class Node{ int to; //가리키는 노드 in..
가장 기본적인 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘을 처음 접한다면 아래 글을 한번 읽어보는 것을 추천한다. 2023.06.26 - [자료구조_알고리즘/Algorithm] - [Algorithm] 다익스트라(dijkstra) 알고리즘 (최단거리, 가중치 그래프) 우선 Edge 클래스를 하나 만들어서 해당 edge가 가리키는 노드, 가중치를 저장한다. 출발 노드는 ArrayList의 index로 관리할 것이기 때문에 필요 없다. 그래프 정보를 저장할 ArrayList[ ] 배열과 최단거리 배열 int[ ] distance를 만들고, 초기화 한다. 각 Edge의 가중치가 작은 것 부터 poll() 할수 있는 우선순위 큐를 만들고 시작점을 먼저 넣는다. 이후 우선순위 큐에서 Edge를 하나씩 꺼내..
