링크상태 알고리즘1 다익스트라(Dijkstra) 알고리즘이란? 다익스트라 알고리즘다익스트라 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 찾는 알고리즘입니다. 1956년 에드가 다익스트라에 의해 제안되었으며, 주로 비가중치 그래프에서 사용됩니다. 다음은 이 알고리즘의 주요 특징과 작동 방식입니다:주요 특징:가중치가 있는 그래프: 다익스트라 알고리즘은 모든 엣지(간선)의 가중치가 비음수일 때 작동합니다.단일 출발지: 하나의 출발 정점에서 다른 모든 정점까지의 최단 경로를 찾습니다.탐욕적 알고리즘: 매 단계에서 가장 가까운 정점을 선택하고 그 정점의 경로를 업데이트합니다.작동 방식:초기화: 시작 정점의 거리를 0으로 설정하고, 나머지 모든 정점의 거리를 무한대로 설정합니다.우선순위 큐: 가장 가까운 정점을 찾기 위해 우선순위 큐(또는 최소 힙)를 사용합.. 2024. 9. 27. 이전 1 다음 728x90 반응형