알고리즘을 위한 간략 정리/그래프 최소비용 (1) 썸네일형 리스트형 [C++] 다익스트라(Dijkstra) 핵심 요약 최단 경로 탐색 알고리즘. 방문한 노드들과 연결된 간선 중 최소 비용인 간선을 선택하는 알고리즘. 단, 가중치가 양수일때만 적용할 수 있다. 동작 원리 '비용' 이라는 말을 많이 사용하게 될 텐데, 이 값은 1차원 배열 Dist[] 라는 배열에 저장되어 있다고 생각하자. 초기 Dist배열의 모든 값은 무한대(INF)로 초기화 되어 있다. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다. 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로 체크해준다. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다. 3 ~ 4번 과정을 반복한다. 구현 1. 비용을 저장.. 이전 1 다음