AI 요약관련 정보

• 최단 경로 알고리즘의 목적은 그래프에서 한 정점에서 다른 정점까지 이동하는 가장 짧은 경로(가중치 총합이 가장 적은 루트)를 찾는 것입니다. 🗺️
• 다익스트라 알고리즘은 단일 시작점에서 모든 다른 정점까지의 최단 거리를 찾는 데 사용됩니다. 📍
• 작동 원리는 시작점에서 각 노드까지의 거리를 무한대로 초기화한 후, 현재까지 발견된 가장 짧은 경로를 지속적으로 업데이트하며 탐색하는 것입니다. 🔄
• 핵심 메커니즘은 가능한 모든 경로를 탐색하며, 기존에 찾은 경로보다 더 짧은 경로를 발견할 때마다 해당 노드의 최단 거리를 갱신하는 것입니다. 💡
• 효율성 향상을 위해 우선순위 큐(최소 힙)를 사용하여 현재까지 발견된 경로 중 가장 짧은 거리를 가진 노드를 먼저 처리합니다. 🚀
• 시간 복잡도는 노드의 수가 V일 때, 일반적으로 O(V^2)입니다. ⏳
• 구현 방식은 인접 리스트(3중 리스트/배열)로 그래프를 표현하고, dist 배열에 최단 거리를 저장하며, 우선순위 큐를 활용하여 탐색을 진행합니다. 💻
• 중요 제약 조건으로, 다익스트라 알고리즘은 간선의 가중치가 음수가 아닌 그래프에서만 올바르게 작동합니다. ⚠️