핵심 정리
| 조건 | 내용 |
|---|---|
| 대상 | 음수 간선이 없는 가중치 그래프 |
| 자료구조 | 우선순위 큐 |
| 시간 | O((V + E) log V) |
| 결과 | 시작점에서 각 정점까지의 최단 거리 |
csharp
var pq = new PriorityQueue<int, long>();
long[] dist = Enumerable.Repeat(long.MaxValue, n).ToArray();
dist[start] = 0;
pq.Enqueue(start, 0);구조
다익스트라는 현재까지 알려진 거리 중 가장 짧은 후보를 먼저 꺼냅니다. 음수 간선이 없으면 가장 짧은 후보로 꺼낸 순간 그 거리는 더 줄어들 수 없어서 확정할 수 있습니다.
text
1. 시작점 거리 0
2. 가장 가까운 후보를 priority queue에서 꺼냄
3. 그 정점의 이웃 거리 완화
4. 더 짧아진 후보를 다시 queue에 넣음거리 완화는 current를 거쳐 next로 가는 길이 기존보다 짧은지 확인하는 과정입니다.
csharp
while (pq.Count > 0)
{
pq.TryDequeue(out int current, out long currentDist);
if (currentDist != dist[current]) continue;
foreach ((int next, int cost) in graph[current])
{
long nextDist = dist[current] + cost;
if (nextDist >= dist[next]) continue;
dist[next] = nextDist;
pq.Enqueue(next, nextDist);
}
}실전 구현에서는 큐에 오래된 거리 후보가 남을 수 있으므로, 꺼낸 거리와 현재 dist를 비교해 버리는 방식이 자주 쓰입니다.
선택 기준
| 문제 조건 | 알고리즘 |
|---|---|
| 간선 비용이 모두 1 | BFS |
| 비용이 양수 또는 0 | 다익스트라 |
| 음수 간선 있음 | 벨만-포드 검토 |
| 모든 쌍 최단 거리, 정점 수 작음 | 플로이드-워셜 |
| 격자에서 휴리스틱 사용 가능 | A*는 별도 영역 |
다익스트라는 최단 거리 문제의 기본 도구지만, 음수 간선이 하나라도 있으면 전제가 깨집니다.
주의할 점
거리 합이 int 범위를 넘을 수 있으면 long을 사용해야 합니다. 간선 비용과 경로 길이를 곱해 최댓값을 먼저 계산하세요.
또 C# PriorityQueue<TElement, TPriority>에서 같은 정점이 여러 번 들어갈 수 있습니다. 오래된 후보를 무시하는 체크를 넣지 않으면 불필요한 탐색이 늘어납니다.
참고 링크
1 sources