다익스트라 (1) 썸네일형 리스트형 Dijkstra의 개념 및 구현 들어가며 오늘은 엄청 유명한 '다익스트라 알고리즘'에 대해 공부해 볼 예정이다. 그래프와 트리에 관한 알고리즘에 특히 약한 편이라 더더 열심히 해야할 것 같다. 개념 및 특징 한 정점에서 나머지 모든 정점까지의 최단 경로를 찾는 알고리즘 음수인 간선을 포함하는 경우 최단 경로를 찾을 수 없는 경우가 있음 구현 연결되지 않은 정점들 간의 거리는 INF(무한대)로 표현 알고리즘 모든 정점을 미방문 상태로 표시한다. 모든 정점 간의 거리를 INF(무한대)로 표시한다. 이어진 정점 간의 거리를 표시한다. 현재 정점(초기값은 시작점)을 방문 상태로 표시한다. 현재 정점과 이어진 정점들에 대해 (시작점에서 현재 정점까지의 거리) + (현재 정점에서 이어진 정점까지 거리) < (시작점에서 이어진 정점까지 거리)을 만.. 이전 1 다음