백준 최소 스패닝 트리 문제를 보면서 대부분 사람들이 크루스칼 알고리즘을 사용하는 것을 봤다.
백준문제-최소 스패닝 트리
크루스칼, 프림 알고리즘은 최소신장트리(minimum spanning tree)를 만들고,
다익스트라, 벨만포드 알고리즘은 최단거리를 구하는 알고리즘이다.
크루스칼vs프림 비교 표
다익스트라vs벨만포드 비교 표
| 비교 항목 | 다익스트라 알고리즘 | 벨만-포드 알고리즘 |
|---|---|---|
| 작동 방식 | 그리디 알고리즘 | 동적 계획법 |
| 음수 가중치 간선 지원 | 음수 가중치 간선을 지원하지 않음 | 음수 가중치 간선을 처리 가능 |
| 최적 부분 경로 구하기 | 루트 노드에서부터 각 노드까지의 최단 경로를 계산 | 루트 노드에서부터 모든 노드까지의 최단 경로를 계산 |
| 음수 가중치 사이클 감지 | 음수 가중치 사이클이 없을 때만 동작함 | 음수 가중치 사이클을 감지하고 처리함 |
| 시간 복잡도 | O(V^2) 또는 O(E log V) (배열 또는 힙을 사용) | O(VE) (모든 간선을 순회) |
| 공간 복잡도 | O(V) (거리 배열 및 힙 또는 배열 사용) | O(V) (거리 배열 및 그래프 저장) |
| 실시간 응용 | GPS 경로 탐색, 네트워크 라우팅에 적합 | 음수 가중치 간선이 있는 네트워크 및 시간 감지 알고리즘에 적합 |
Work as though your strength were limitless. <S. Bernhardt>