자료구조_알고리즘/Algorithm
[Algorithm/Java] 다익스트라(dijkstra) 알고리즘 (최단거리, 가중치 그래프)
다익스트라(dijkstra) 알고리즘 다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘이다. 가중치 그래프 상에서 출발노드에서 목표노드까지 이동하는 가장 짧은 경로를 찾는 방법을 찾는다. 하나의 출발 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있다. 에지(간선)은 모두 양수여야 한다. 시간 복잡도 : O(ElogV) 그리디와 DP의 특성을 갖고 있다. 다익스트라 알고리즘 동작 원리 1. 인접 리스트로 그래프를 구현한다. [1] ->[ 2, 8 ] 은 1에서 2로 가는 가중치가 8이라는 뜻이다. 실제로는 아래와 같이 Edge 클래스를 만들어서 Edge 형 ArrayList배열을 선언하여 구성하였다. ArrayList[] graph; class Node{ int to; //가리키는 노드 in..
