Dijkstra
-
알고리즘, graph, DijkstraData Structure & Algorithm 2024. 7. 3. 18:18
다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 데 사용되는 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 사용되며, 가중치가 음수가 아닌 경우에만 적용할 수 있습니다.다익스트라 알고리즘의 개념시작 정점 선택: 알고리즘은 시작 정점에서 시작합니다.최단 경로 집합: 최단 경로를 확정한 정점들의 집합을 유지합니다.미확정 집합: 아직 최단 경로가 확정되지 않은 정점들의 집합을 유지합니다.거리 배열: 시작 정점에서 각 정점까지의 현재까지 발견된 최단 거리를 저장합니다. 초기에는 시작 정점의 거리를 0으로 설정하고 나머지 정점의 거리를 무한대로 설정합니다.이웃 정점 업데이트: 현재 정점에서 인접한 정점들로의 거리를 계산하고, 더 ..