Heap (1) 썸네일형 리스트형 [알고리즘] Dijkstra 최단 경로 알고리즘에는 다양한 종류의 알고리즘이 있는데 그 중에서 Dijkstra는 하나의 시작점에서 다른 모든 노드까지의 거리의 최소를 알려준다. Dijkstra 알고리즘을 사용하기 위한 조건으로는 하나의 시작점이 정해져있을 것, 그리고 음수 값을 가진 간선이 없을 것이다. Greedy 적인 방법으로 접근하기 때문에 음수 값의 간선이 존재하면 알고리즘이 성립하지 않는다. 자세한 설명들은 다른 블로그에 잘 나와있으니까.. 헷갈릴 만한 개념들만 되짚어보자. 진행 방향은 다음과 같다. 초기조건 : 일차원 Distance를 저장할 수 있는 배열(이하 Dist[]). 무한대에 비슷한 큰 값을 넣어준다. 시작 집합에 시작점을 넣어준다. 알고리즘 : 1. 시작집합과 연결된 노드 중 가장 거리가 짧은 노드(이하 a).. 이전 1 다음