dijstra1 [최단경로] 다익스트라(Dijstra) 알고리즘 30. 최단 경로 알고리즘 BFS와 구현방법이 상당히 비슷하다. 다익스트라 알고리즘 다익스트라(Dijstra, 데이크스트라) 알고리즘은 다음과 같다. d[v]는 시작점 s로 부터 그래프의 모든 점까지의 최단거리이다. 아이디어는 BFS와 비슷한데, 가중치가 붙어있는 그래프를 다루므로, queue에 넣을 때는 (지금까지 누적 cost, 다음점)을 넣어준다. 매번 while문의 처음에서 cost가 최소인 점을 선택하는 이유는, 최단 거리가 되는 가능성이 있는 점들을 먼저 탐색하고 d[v]를 기록해주기 위함이다. 이렇게 해서 S 안에 다른 원소가 뽑혀 이미 기록된 d[v] 과 비교하여 더 크다면, 무시해주면 된다! 그래프를 직접 그려보면서, 알고리즘을 이해하는 것이 효율적인 것 같다. 이렇게 해서 직접 코드를 .. 2019. 9. 27. 728x90 이전 1 다음
