반응형 그래프최단경로1 [Graph] 다익스트라(Dijkstra) 알고리즘 - 다익스트라 DP를 활용한 정점과 정점 사이의 최단거리를 알아내는 최단경로알고리즘이다. 하나의 출발지에서 모든 정점을 도착지로 한 최단경로를 구할 수 있다. 이때 음의 간선은 포함할 수 없다. Step1. 방문하지 않은 정점 중 S -> 자신으로의 비용이 최소인 정점 선택 Step2. 선택한 정점을 경유지로 해서 아직 방문하지 않은 다른 정점과의 비용을 계산해서 최적을 갱신 - 이전에 선택된 정점은 경유지를 통해 가는 것 보다 무조건 더 짧기 때문에 고려 X 위 상태에서는 시작점 s(0)를 시작으로 갈 수 있는 정점인 t(10), y(5)을 우선순위 큐에 넣는다. 큐는 가중치가 작은 순서대로 정렬므로 y(5)를 기준으로 다시 탐색한다. 이 과정에서 t(10)은 s->y->t(8)의 비용이 더 저렴하므로.. 2021. 9. 30. 이전 1 다음
