- 최단 경로란 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에서 간선의 가중치의 합이 최소인 경로
- 가중치가 없다면 BFS, 가중치가 있고 단일 출발점에서의 최단경로는 다익스트라, 벨만-포드 알고리즘, 모든 정점에 대해 최단 경로를 구한다면 플로이드-와샬 알고리즘
- 모든 쌍 최단 경로 문제는 그래프 내의 모든 정점 쌍 (i, j)에 대해 i에서 j까지의 최단 경로를 찾는 문제를 의미
- 사실상 다익스트라나 펠만-포드는 APS 안의 개념보다는 반복을 통해 해당 문제를 풀 수 있는 방법이라고 함
- 해당 두 가지 방법은 APS보다는 단일 출발점 최단 경로 (SSSP, Single Source Shortest Path) 문제를 해결하는 알고리즘임
- 주어진 그래프에서 정점 A에서 B, C, D 등 다른 모든 정점들 까지의 최단 경로를 찾는 것이 아니라 그래프의 모든 정점들 사이의 최단 경로를 모두 구하는 문제
- 동적 프로그래밍을 이용해 모든 정점 쌍 사이의 최단 경로를 구함
- 모든 정점들에 대한 최단 경로로 APS 문제를 해결하는데 직접적으로 사용되는 알고리즘
- 시간복잡도는 O(V^3)로 그래프의 정점 수가 많을 때는 계산이 오래 걸림
- 가중치가 음수일 수 있는 그래프에도 적용할 수 있으나 사이클이 존재하면 정확하지 않음
- 다익스트라 알고리즘은 모든 정점에 대해 반복 적용하여 APS를 구할 수 있음
- 단일 출발점 최단 경로(Single Source Shortest Path, SSSP)를 해결하는 알고리즘
- 하나의 시작 정점에서 끝 정점까지의 최단 경로
- 시간복잡도는 O(V^3) 또는 O(V^2 log V + VE)가 됨
- 음수 가중치를 가지지 않는 그래프에 적용 가능
- 플로이드-와샬과 함께 둘 다 최단 경로를 찾는 알고리즘이지만, 그 적용 범위와 효율성에서 차이가 있음
- 단일 출발점 최단 경로(Single Source Shortest Path, SSSP)를 해결하는 알고리즘
- 하나의 시작 정점에서 끝 정점까지의 최단 경로
- 단일 출발점에서 다른 모든 정점까지의 최단 경로를 구하는 방법으로 음수 가중치가 있는 그래프에서 최단 경로를 찾을 수 있음
| 알고리즘 | 문제 유형 | 가중치 조건 | 시간 복잡도 | 주요 특징 | APS 해결 여부 |
|---|---|---|---|---|---|
| 다익스트라 | 단일 출발점 최단 경로 (SSSP) | 양수 가중치만 | O((V + E) log V) | 우선순위 큐를 사용하여 효율적, 음수 가중치 불가능 | 반복 사용 시 가능 |
| 벨만-포드 | 단일 출발점 최단 경로 (SSSP) | 음수 가중치 가능 | O(V * E) | 음수 가중치 허용, 음수 사이클 감지 가능 | 반복 사용 시 가능 |
| 플로이드-와샬 | 모든 정점 쌍 최단 경로 (APSP) | 음수 가중치 가능 | O(V^3) | 동적 프로그래밍을 사용하여 모든 정점 쌍 간의 최단 경로 계산 | 가능 |
- 시작정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
- 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식
- 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사함
- 다익스트라 알고리즘은 출발점에서 특정 목적지까지 가는 최단 경로를 찾는 알고리즘
- 한 정점에서 다른 정점으로 가는 최단 경로를 찾는 것이 목표
- 프림 알고리즘은 모든 정점을 포함하는 최소 신장 트리를 찾는 알고리즘
- 그래프의 모든 정점을 포함하는 트리를 만들며 이 트리에서 사용된 간선들의 가중치 합이 최소가 되도록 함
| 구분 | 다익스트라 알고리즘 (Dijkstra) | 프림 알고리즘 (Prim) |
|---|---|---|
| 목적 | 단일 출발점에서 다른 모든 정점까지의 최단 경로 찾기 | 모든 정점을 포함하는 최소 신장 트리(MST) 찾기 |
| 결과물 | 출발점에서 목적지까지의 최단 경로 (하나의 경로) | 모든 정점을 연결하는 최소 비용 트리 (트리 구조) |
| 문제 유형 | 단일 출발점 최단 경로 문제 (SSSP) | 최소 신장 트리 문제 (MST) |
| 작동 방식 | 출발점에서 시작해, 최단 경로를 확장해 나감 | 임의의 정점에서 시작해, 최소 비용으로 트리를 확장 |
| 적용 대상 | 경로의 최소 가중치를 찾는 문제 | 모든 정점을 연결하는 최소 비용을 찾는 문제 |
| 가중치 조건 | 양수 가중치만 가능 | 양수 및 음수 가중치 모두 가능 |
| 사용 예 | 네트워크 라우팅, GPS 내비게이션 | 전력망, 통신망, 도로망 설계 등 |
| 동작 방식 예 | A에서 B로 가는 가장 빠른 길을 찾는 문제 | 모든 도시를 최소 비용으로 연결하는 도로망을 찾는 문제 |