알고리즘2 [JAVA] 다익스트라(dijkstra) 자바로 구현하기 인접행렬, 우선순위큐 다익스트라를 자바로 구현해보자. 다익스트라의 개념에 대해서는 밑에 게시글을 참고 바란다. [Algorithm] 다익스트라(Dijkstra) 알고리즘 자바, 파이썬 [Algorithm] 다익스트라(Dijkstra) 알고리즘 자바, 파이썬 개요 다익스트라(Dijkstra) 알고리즘은 BFS와 DP를 활용한 최단경로 탐색 알고리즘이다. 다이나믹 프로그래밍인 이유는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 gomgomkim.tistory.com 구현에는 인접 행렬 방식, 우선순위 큐 방식이 있다. 노드의 개수를 V라고 할 때 인접 행렬 방식은 O( V^2 ) 우선순위 큐 방식은 O( V log V ) 의 시간 복잡도를 가진다. 따라서 알고리즘 문제풀이 시 우선순위 큐 방식을 추천.. Java 2021. 4. 12. 더보기 ›› [Algorithm] 다익스트라(Dijkstra) 알고리즘 자바, 파이썬 개요 다익스트라(Dijkstra) 알고리즘은 BFS와 DP를 활용한 최단경로 탐색 알고리즘이다. 다이나믹 프로그래밍인 이유는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다. 특징 그래프 내부 하나의 정점(노드, Vertex)에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 그래프의 간선(Edge)마다 가중치가 존재할 때 사용한다. 이 점이 BFS를 활용한 최단 경로 구하기와 다른 점이다. 간선의 음의 가중치는 존재하지 않는다. 음의 가중치가 하나라도 있으면 다익스트라를 사용할 수 없다. 음의 가중치가 존재하지 않기 때문에 현실 세계에 사용하기 적합한 알고리즘이다. (ex. GPS, 내비게이션) 출발 노드, 도착 노드로 구성된 이차원 배열 활용 구현과 각 거.. Algorithm 2021. 4. 8. 더보기 ›› 이전 1 다음
