다익스트라1 [알고리즘] Dijkstra 다익스트라 알고리즘 다익스트라 알고리즘이란? 첫 정점을 기준으로 연결되어있는 정점을 추가해가며 최단거리를 갱신하는 기법이다. 어떤 문제를 풀 수 있는가? 한 정점에서 출발하여 그래프 내 다른 모든 정점까지의 가장 짧은 경로를 찾을 수 있다. 다익스트라 알고리즘 로직 첫 정점부터 각 노드간의 거리를 저장할 배열을 선언한 후, 첫 정점에서 인접 노드간의 거리를 계산하면서 첫 정점~해당 노드 간의 가장 짧은 거리를 해당 배열에 업데이트한다. 를 이용한 다익스트라 알고리즘 (minHeap) 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장한다. 초기에 첫 정점의 거리는 0, 나머지는 무한대로 저장한다. (Integer.MAX_VALUE) 우선순위 큐에 삽입한다. 우선순위 큐에서 노드를 꺼낸다. 꺼낸 노드의.. 2021. 3. 30. 이전 1 다음