Dijkstra 알고리즘

Dijkstra 알고리즘

가중치가 양수인 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 탐욕 알고리즘

목적: 단일 출발 최단 경로, 양수 가중치

특징: 탐욕 알고리즘, 우선순위 큐, 양수 가중치만

동작 상세

Relaxation: dist[v] > dist[u] + weight(u, v)면 갱신

음수 가중치 불가 이유: 이미 확정된(방문 처리된) 정점의 거리가 이후에 더 짧아질 수 있어 탐욕 선택 원리가 깨짐

구현 방식별 시간 복잡도

공간 복잡도: O(V) - 거리 배열 + 우선순위 큐

장점: 효율적(O((V+E) log V)), 정확, 양수 가중치에 최적

단점: 음수 가중치 불가, 모든 정점 탐색(단일 목적지도)

적용사례: GPS 내비게이션, 네트워크 라우팅(OSPF), 게임 경로, 지도 앱

비교: Dijkstra(양수/빠름) vs Bellman-Ford(음수/느림) vs A*(휴리스틱/빠름)

연관: 탐욕, 우선순위 큐, 최단 경로, Bellman-Ford, A*