목록다익스트라 #알고리즘 #최단경로 #다익스트라 알고리즘 #C++ (1)
개발자 김수진
[알고리즘] 다익스트라(Dijkstra)
[개념] 다익스트라 알고리즘이란 하나의 정점에서부터 다른 정점들까지의 최단거리를 구하는데 사용되는 탐색 알고리즘이다. 정점까지의 최단 경로를 구할 때 , 이전에 구한 다른 정점들까지의 최단 경로를 구한다. 1. 출발 정점을 구한다 2. 출발 정점과 인접한 점들을 방문 처리한다. 3. 출발 정점과 인접한 점들 중에서 비용이 가장 적은 정점으로 간다. 4. 다음 정점에서 마찬가지로 2,3번을 반복한다. 위의 과정을 반복할 때 한번 방문했던 정점은 재방문 하지않는다. 3번의 과정을 통해 최단 경로를 보장할 수 있다. 현재 정점을 기준으로 비용이 가장 적은 정점으로 가므로 이것이 최단 경로가 되는 것이다. 위의 그래프를 기준으로 각 정점들의 거리를 배열에 초기화하면 다음과 같이 된다. 1 2 3 4 5 6 1 ..
카테고리 없음
2022. 8. 16. 00:55