우선순위 큐1 [Algorithm] 다익스트라(Dijkstra) 알고리즘 자바, 파이썬 개요 다익스트라(Dijkstra) 알고리즘은 BFS와 DP를 활용한 최단경로 탐색 알고리즘이다. 다이나믹 프로그래밍인 이유는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다. 특징 그래프 내부 하나의 정점(노드, Vertex)에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 그래프의 간선(Edge)마다 가중치가 존재할 때 사용한다. 이 점이 BFS를 활용한 최단 경로 구하기와 다른 점이다. 간선의 음의 가중치는 존재하지 않는다. 음의 가중치가 하나라도 있으면 다익스트라를 사용할 수 없다. 음의 가중치가 존재하지 않기 때문에 현실 세계에 사용하기 적합한 알고리즘이다. (ex. GPS, 내비게이션) 출발 노드, 도착 노드로 구성된 이차원 배열 활용 구현과 각 거.. Algorithm 2021. 4. 8. 더보기 ›› 이전 1 다음
