최단 경로 알고리즘 다익스트라
최단 경로 알고리즘: 다익스트라
다익스트라(Dijkstra) 알고리즘은 그래프에서 하나의 시작 정점(Single Source)으로부터 다른 모든 정점까지의 최단 경로를 찾는 대표적인 알고리즘입니다. 이 알고리즘은 간선의 가중치가 음수가 아닌 경우에만 정확한 결과를 보장하며, 그리디(Greedy) 접근 방식을 사용합니다.
🗺️ 다익스트라 알고리즘의 동작 원리
- 핵심 아이디어 : 시작 정점에서부터 출발하여, 각 정점까지의 최단 거리를 점차적으로 확정해 나갑니다. '현재까지 알려진 최단 거리가 가장 짧은 정점'을 우선적으로 탐색합니다.
- 필요한 자료구조
> * `dist` 배열: 시작 정점에서부터 각 정점까지의 최단 거리를 저장. 처음에는 시작 정점은 0, 나머지는 무한(infinity)으로 초기화합니다. > * 우선순위 큐 (Priority Queue) : 다음에 방문할 정점을 효율적으로 선택하기 위해 사용합니다. (방문하지 않은 정점 중, `dist` 값이 가장 작은 정점을 선택)
- 동작 과정
1. `dist` 배열을 무한으로, 시작 정점은 0으로 초기화하고, 우선순위 큐에 (거리 0, 시작 정점)을 넣습니다. 2. 우선순위 큐에서 거리가 가장 짧은 정점 `u`를 꺼냅니다. 3. 만약 `u`가 이미 처리된 정점이라면(꺼낸 정점의 거리가 `dist` 배열의 값보다 크다면) 무시합니다. 4. `u`와 인접한 모든 정점 `v`에 대해, `u`를 거쳐 `v`로 가는 새로운 경로(`dist[u] + weight(u,v)`)가 기존의 `dist[v]`보다 짧다면, `dist[v]`를 갱신하고 우선순위 큐에 (갱신된 거리, `v`)를 넣습니다. 5. 우선순위 큐가 빌 때까지 2~4번 과정을 반복합니다.
🆚 다른 최단 경로 알고리즘과의 비교
- 벨만-포드 알고리즘 (Bellman-Ford)
> * 음수 가중치가 있는 그래프에서도 동작 가능하며, 음수 사이클(negative cycle)의 존재 여부를 감지할 수 있습니다. > * 시간 복잡도가 O(VE)로, 다익스트라(O(E log V))보다 느립니다.
- 플로이드-워셜 알고리즘 (Floyd-Warshall)
> * 모든 정점에서 다른 모든 정점까지의 최단 경로를 한 번에 구합니다. > * 시간 복잡도가 O(V³)로, 정점의 개수가 적을 때 유용합니다.
💡 개발자 핵심 Point
- 다익스트라 알고리즘은 음수 가중치가 없는 그래프의 단일 출발점 최단 경로 문제에 가장 효율적인 해결책입니다.
- 그리디 알고리즘 : 매 단계에서 '현재까지 알려진 최단 거리가 가장 짧은 정점'을 선택하는 것이 그리디적인 선택이며, 이 선택이 전체의 최적해로 이어짐이 증명되어 있습니다.
- 우선순위 큐의 중요성 : 다음에 방문할 정점을 찾기 위해 매번 모든 정점을 순회하면 O(V²)의 시간 복잡도를 갖게 됩니다. 우선순위 큐(힙)를 사용하면 이 과정을 O(log V)로 단축하여, 전체 시간 복잡도를 O(E log V)로 만들 수 있습니다.
- 활용 사례 : 내비게이션 시스템(도로망), 네트워크 라우팅 프로토콜(OSPF) 등에서 최적의 경로를 찾는 데 널리 사용됩니다.
