다익스트라(Dijkstra) 알고리즘
·
알고리즘/study
다익스트라(Dijkstra) 알고리즘가중그래프에서 특정 하나의 노드에서 다른 모든 노드로의 최단 거리 정보를 알아내는 알고리즘이다.음수 가중치를 갖는 간선을 포함한 그래프에서는 올바르게 동작하지 않는다. (음수 가중치가 있을 경우 최단 경로가 계속 갱신될 수 있기 때문에)구현 특징문제를 그래프로 표현하여 각 정점 연결 상황을 저장한다.정점 간 최단 거리 정보(distance)를 1차원 리스트에 저장하며 리스트를 계속해서 갱신한다.매 단계마다 아직 방문하지 않은 정점 중 최단 거리인 정점을 찾아 방문하여 최단거리를 확정하고, 이를 반복하는 방식이다.방문하지 않은 정점 중에서 최단 거리가 최소인 정점을 찾는 과정에서 Heap, Priority Queue를 이용한다.구현 방법출발 노드(s) 설정최단 거리 테이..