Quick Reference
음수 간선이 없는 가중치 그래프에서 시작점 하나의 최단 거리를 구할 때 사용합니다. 우선순위 큐에서 꺼낸 거리와 현재 최선 거리가 같은 후보만 확장하면, 같은 정점이 여러 번 들어가도 안전합니다.
| 간선 비용 조건 | 먼저 고를 알고리즘 |
|---|---|
모두 1 | BFS |
0 또는 1 | 0-1 BFS |
| 모두 0 이상 | 다익스트라 |
| 음수 포함 | Bellman-Ford |
구조
다익스트라는 현재까지 알려진 거리 중 가장 짧은 후보를 먼저 꺼냅니다. 음수 간선이 없으면 가장 짧은 후보로 꺼낸 순간 그 거리는 더 줄어들 수 없어서 확정할 수 있습니다. 인접 리스트와 이진 힙 우선순위 큐를 쓰면 시간은 O((V + E) log V), 거리·이전 정점·큐를 위한 공간은 O(V + E)입니다.
1. 시작점 거리 0
2. 가장 가까운 후보를 priority queue에서 꺼냄
3. 그 정점의 이웃 거리 완화
4. 더 짧아진 후보를 다시 queue에 넣음거리 완화는 current를 거쳐 next로 가는 길이 기존보다 짧은지 확인하는 과정입니다. C# PriorityQueue<TElement, TPriority>는 decrease-key를 제공하지 않으므로, 더 짧아진 거리를 새로 넣고 꺼낼 때 오래된 후보를 버립니다.
static (long[] Distance, int[] Previous) ShortestPaths(
IReadOnlyList<(int To, long Cost)>[] graph,
int start)
{
const long INF = long.MaxValue / 4;
long[] distance = Enumerable.Repeat(INF, graph.Length).ToArray();
int[] previous = Enumerable.Repeat(-1, graph.Length).ToArray();
var queue = new PriorityQueue<int, long>();
distance[start] = 0;
queue.Enqueue(start, 0);
while (queue.TryDequeue(out int current, out long currentDistance))
{
if (currentDistance != distance[current]) continue;
foreach ((int next, long cost) in graph[current])
{
if (cost < 0) throw new ArgumentOutOfRangeException(nameof(graph));
if (currentDistance > INF - cost) continue;
long nextDistance = currentDistance + cost;
if (nextDistance >= distance[next]) continue;
distance[next] = nextDistance;
previous[next] = current;
queue.Enqueue(next, nextDistance);
}
}
return (distance, previous);
}INF보다 큰 실제 경로는 이 구현 범위 밖입니다. 입력의 최대 간선 비용과 최대 간선 수를 곱해, 가능한 최단 거리가 INF보다 충분히 작은지 먼저 확인합니다. 도달하지 못한 정점은 distance[v] == INF로 남습니다.
경로 복원
완화할 때 직전 정점 previous[next]를 함께 저장하면 거리뿐 아니라 실제 경로도 복원할 수 있습니다. 목표 하나만 필요하면 유효한 후보로 목표를 dequeue했을 때 탐색을 멈춰도 됩니다.
static List<int> RestorePath(int start, int goal, int[] previous)
{
if (start != goal && previous[goal] == -1) return [];
var path = new List<int>();
for (int current = goal; current != -1; current = previous[current])
{
path.Add(current);
}
path.Reverse();
return path;
}선택 기준
| 문제 조건 | 알고리즘 |
|---|---|
| 간선 비용이 모두 1 | BFS |
| 비용이 양수 또는 0 | 다익스트라 |
| 음수 간선 있음 | 벨만-포드 검토 |
| 모든 쌍 최단 거리, 정점 수 작음 | 플로이드-워셜 |
| 격자에서 휴리스틱 사용 가능 | A*는 별도 영역 |
다익스트라는 최단 거리 문제의 기본 도구지만, 음수 간선이 하나라도 있으면 전제가 깨집니다. 동점 priority의 dequeue 순서는 경로 하나를 고르는 문제에서 고정되지 않으므로, 사전순처럼 특정 경로를 요구하면 priority와 이전 정점 갱신 규칙을 별도로 설계해야 합니다.
주의할 점
거리 합이 int 범위를 넘을 수 있으면 long을 사용해야 합니다. 간선 비용과 경로 길이를 곱해 최댓값을 먼저 계산하고, long.MaxValue 자체를 INF로 더하지 마세요. 도달 불가능 표식과 실제 거리의 덧셈이 overflow를 만들 수 있습니다.
또 C# PriorityQueue<TElement, TPriority>에서 같은 정점이 여러 번 들어갈 수 있습니다. 오래된 후보를 무시하는 체크를 넣지 않으면 불필요한 탐색이 늘어납니다.
참고 링크
2 sources