CS 전공지식/알고리즘 (1) 썸네일형 리스트형 [알고리즘] Dijkstra 알고리즘 Dijkstra 알고리즘 - 정의 Dijkstra 알고리즘은 하나의 정점에서 나머지 정점까지의 최단 거리(경로)를 구하는 알고리즘입니다. 정점 사이에 간선이 존재하고, 간선마다 가중치(=비용)가 있습니다. 특징으로는 모든 가중치가 양수일 때만 사용할 수 있는 알고리즘입니다. 어떠한 정점에 방문할 때 이전의 선택했던 경로가 아니라 다른 경로를 거쳐 방문하는 것이 더 적은 비용이 든다면, 다른 경로를 거쳐 방문하면서 최단 거리를 구합니다. 말로만 설명하면 이해하기 어려우니 과정을 보면서 설명하겠습니다. - 최단거리를 구하는 과정 위의 그래프는 정점이 5개, 간선이 6개이며 각 간선에는 가중치가 표시되어 있습니다. distance배열은 시작 정점이 1일 때 각 정점으로 갈 수 있는 최소 비용을 저장합니다. 아.. 이전 1 다음
