다익스트라1 최단거리구하기_다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘에 대한 이해 - 하나의 정점으로 부터 다른 모든 정점까지의 최단거리를 구하는 문제이다. - 음수 간선이 있는 그래프에서는 사용할 수 없다. - 우선순위큐를 이용한다. V = 6, E = 7인 다음 그래프에 대하여, 정점 1번으로 부터 다른 모든 정점까지의 거리를 구해보자. 1번으로부터의 거리를 저장하는 dist 배열을 구성하고, 우선순위 큐에 1번 노드의 (거리, 노드번호)를 추가한다. 우선순위 큐는 가장 작은 값을 먼저 뱉어내므로, 1번으로부터의 거리가 가장 가까운 노드를 뽑아내면 (0, 1)이 된다. 이 때, 큐에서 뽑아낸 (0, 1)의 정보와 배열의 정보 dist[1] = 0이 일치하므로 1번까지의 거리를 확정한다. 1번에서 이동할 수 있는 노드는 2번 노드 뿐이다. 거리가 확정.. 2022. 8. 29. 이전 1 다음