개발/알고리즘 (1) 썸네일형 리스트형 Dijkstra's algorithm(데이크스트라 알고리즘) 1.정의 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘 최단 경로(Shortest Path)를 찾는 대표적인 기법 가중치가 음수인 경우 작동하지 않는다. 그래프 전체에서 가장 작은 가중치의 절대값만큼 모든 간선의 가중치를 더해줘서 알고리즘을 적용할 수 있다. 2.이용 사례 내비게이션: 지도상의 각 도시들을 정점으로, 도로들을 간선으로 갖는 그래프 지하철도 가능하다. 3.알고리즘 1) 출발지 정점을 제외한 모든 정점의 거리정보를 무한대로 초기화 한다. - 노드 및 거리는 우선순위 큐에 Enqueue 2) 거리가 제일 작은 정점을 Dequeue(최초는 출발지 정점이 된다.) 3) 해당 정점과 연결된 정점들의 거리를 업데이트한다. - 최초 거리는 무한대 이므로 무조건 업데.. 이전 1 다음