자료구조 및 알고리즘/이론
-
[Java] 다익스트라(Dijkstra, 데이크스트라) 알고리즘자료구조 및 알고리즘/이론 2017. 11. 7. 23:07
다익스트라 알고리즘은 아래의 상황에서 사용합니다. 1. 음수 가중치가 존재하지 않는 방향성 그래프이며2. 시작점이 주어지고 다른 모든 노드까지의 거리를 구하는 경우에 이 알고리즘의 시간복잡도는 노드의 수를 V, 간선의 수를 E 이라고 가정할 때 O((V + E)logV) 입니다. 그렇기 때문에 특히 노드의 수 제곱에 비해 간선의 수가 적은 희소그래프에서 주로 사용되며, cost 가 가장 작은 노드 선택을 위해 정점들을 Heap 형태로 저장합니다. 아래는 해당 다익스트라 알고리즘을 Java 로 구현한 내용입니다. import java.io.BufferedWriter; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.uti..