다익스트라 알고리즘1 [그래프] 다익스트라 알고리즘 (Dijkstra algorithm) 다익스트라 알고리즘 에지에 가중치가 있는 그래프(weighted graph)에서 최단 경로를 찾는 알고리즘 에지의 가중치가 양수일때만 사용 가능하다. 시작 노드 S로부터 다른 모든 노드까지의 최단 경로를 찾는다. 기본 원리 필요한 자료구조 노드 사이의 관계를 표현할 그래프: graph 시작 노드로부터 각 정점까지의 거리를 기록할 배열: distance 최단 경로가 확정된 노드를 꺼내올 최소힙: min_heap 우선 시작 노드를 제외한 모든 노드의 비용을 가장 큰 값(이를테면, 무한대)으로 초기화한다. 시작 노드를 최소힙에 넣는다. 최소힙에서 노드를 꺼낸 후 인접한 노드를 확인한다. 이때, 인접한 노드로 이동하는 비용(현재까지의 비용+이동하는데 드는 비용)이 해당 노드에 기록되어있는 값보다 작다면? 값을 .. 2021. 7. 27. 이전 1 다음