Dijkstra
-
Dijkstra알고리즘 2020. 3. 17. 15:02
그래프에서 정점끼리의 최단 경로를 구하는 알고리즘에는 다익스트라, 벨만-포드, 플로이드가 존재한다.이번에는 다익스트라에 대해서 알아보도록 한다. Dijkstra algorithm 다익스트라 알고리즘개념 : 하나의 정점에서 다른 모든 정점들의 최단 경로를 구하는 방법구현 방식 : priority queue 사용 (priority queue는 내림차순으로 정렬해줌을 주의)작동 방식첫 정점을 기준으로 연결되있는 정점들을 추가하며, 최단 거리를 갱신한다.(거리를 저장하는 배열의 초기값은 무한대 값으로 저장한다.) 그림 예시 (파란색은 각 정점 사이의 가중치를 뜻한다.)정점이 7개 있을때의 그래프 1을 중심으로 다른 정점들까지의 최단 거리를 구한다고 하면, 거리 배열은이런 모습으로 만들어진다.만약, 다른 정점으로..