가중치 그래프와 최단 경로 알고리즘 (Dijkstra & A*) 정리
가중치 그래프와 최단 경로 알고리즘 (Dijkstra & A*)
1. 가중치 그래프 (Weighted Graph)
일반적인 BFS는 모든 간선의 비용이 동일하다는 전제에서 최단 경로를 보장한다.
하지만 실제 문제에서는 이동하는 경로나 위치에 따라 비용이 달라지는 경우가 많다.
가중치가 필요한 이유
- 지도에서 고속도로와 일반 도로는 이동 시간이 다르다.
- 게임 맵에서 평지, 언덕, 장애물 주변의 이동 비용은 다를 수 있다.
- 네트워크에서는 경로마다 전송 비용이나 지연 시간이 다를 수 있다.
이처럼 간선이나 이동에 비용을 부여한 그래프를 가중치 그래프라고 한다.
프로젝트의 가중치 표현
이 프로젝트에서는 GraphNode의 weight 필드를 이용하여 해당 노드로 이동하는 비용을 표현한다.
public class GraphNode
{
public int weight = 1;
}
이 구조에서는 노드의 가중치를 해당 노드에 진입할 때 발생하는 비용으로 취급한다.
따라서 현재 노드에서 인접 노드로 이동할 때 인접 노드의 weight를 누적한다.
2. Dijkstra 알고리즘
Dijkstra(다익스트라) 알고리즘은 음수 가중치가 없는 그래프에서 시작 정점으로부터 다른 정점까지의 최단 경로를 구하는 알고리즘이다.
핵심 아이디어
현재까지 계산된 거리 중 가장 작은 값을 가진 미방문 정점을 선택하여 처리한다.
이러한 방식을 탐욕 선택(Greedy Selection)이라고 한다.
음수 가중치가 없다는 조건에서는 가장 가까운 정점의 최단 거리를 확정할 수 있다.
거리 초기화
알고리즘을 시작할 때 모든 정점까지의 거리를 초기화한다.
- 시작 정점의 거리: 0
- 나머지 정점의 거리: 무한대(∞)
시작 정점의 거리를 0으로 설정하는 이유는 시작 정점에서 다른 정점으로 이동할 때 발생하는 비용만 누적하기 위해서이다.
따라서 시작 정점 자체의 weight는 최초 이동 비용에 포함하지 않는다.
동작 과정
- 시작 정점의 거리를 0으로 설정한다.
- 시작 정점과 우선순위 0을 우선순위 큐에 추가한다.
- 우선순위 큐가 빌 때까지 반복한다.
- 큐에서 거리가 가장 작은 정점을 꺼낸다.
- 이미 방문한 정점이면 건너뛴다.
- 목적지에 도달했다면 탐색을 종료할 수 있다.
- 현재 정점과 연결된 인접 정점들을 확인한다.
- 현재 정점까지의 거리와 인접 정점의 이동 비용을 더한다.
- 새로 계산한 거리가 기존 거리보다 작으면 거리를 갱신한다.
- 이전 정점 정보를 기록하고 우선순위 큐에 추가한다.
거리 갱신 공식
newDist = distances[current] + adjacent.weight
현재 정점까지의 누적 비용에 다음 정점으로 진입하는 비용을 더한다.
새로운 거리가 기존 거리보다 작으면 다음 정보를 갱신한다.
distances[adjacent]: 새로운 최단 거리adjacent.previous: 현재 정점- 우선순위 큐: 새로운 거리와 정점을 추가
우선순위 큐를 사용하는 이유
Dijkstra는 매번 가장 가까운 미방문 정점을 선택해야 한다.
Min-Heap 기반 우선순위 큐를 사용하면 가장 작은 거리의 정점을 효율적으로 가져올 수 있다.
우선순위 큐에서 이미 처리한 정점이 다시 나올 수 있으므로 방문 여부를 확인하여 중복 처리를 방지한다.
시간 복잡도
우선순위 큐를 사용하는 일반적인 구현의 시간 복잡도는 다음과 같다.
O((V + E) log V)
- V: 정점의 수
- E: 간선의 수
우선순위 큐 대신 매번 모든 정점을 선형 탐색하여 최솟값을 찾으면 일반적으로 O(V²)의 시간이 필요하다.
Dijkstra의 한계
- 음수 가중치가 있는 그래프에서는 최단 경로를 보장하지 못한다.
- 시작 정점에서 여러 방향으로 탐색이 퍼질 수 있다.
- 목적지가 가까워도 목적지와 관계없는 방향을 탐색할 수 있다.
음수 가중치가 필요한 경우에는 Bellman-Ford와 같은 다른 알고리즘을 고려해야 한다.
목적지 방향으로 탐색을 유도하려면 A* 알고리즘을 사용할 수 있다.
3. A* 알고리즘
A*(A-Star)는 현재까지의 실제 이동 비용과 목적지까지의 예상 비용을 함께 고려하는 최단 경로 탐색 알고리즘이다.
Dijkstra가 현재까지의 이동 비용만 고려한다면 A*는 목적지까지 얼마나 남았는지도 함께 고려한다.
핵심 공식
f(n) = g(n) + h(n)
g(n): 시작 정점에서 현재 정점까지의 실제 이동 비용이다.h(n): 현재 정점에서 목적지까지의 예상 이동 비용이다.f(n): 현재까지의 비용과 예상 비용을 합한 값이다.
A*는 f(n)을 우선순위로 사용하여 다음에 탐색할 정점을 선택한다.
휴리스틱 (Heuristic)
휴리스틱은 현재 위치에서 목적지까지의 비용을 추정하는 함수이다.
실제 비용을 모두 계산하지 않고 목적지와의 거리를 예상하여 탐색 방향을 결정하는 데 사용한다.
허용 가능한 휴리스틱 (Admissible Heuristic)
최단 경로를 보장하기 위해 사용하는 중요한 조건이다.
h(n) ≤ 실제 n에서 목적지까지의 최저 비용
휴리스틱이 실제 최저 비용보다 크게 추정하지 않아야 한다.
즉, 실제보다 비용을 낮게 추정하거나 정확하게 추정해야 최적 경로를 보장할 수 있다.
4. 격자 그래프의 휴리스틱 종류
격자 기반 길찾기에서는 이동 가능한 방향에 따라 적절한 휴리스틱을 선택한다.
Manhattan Distance
|dx| + |dy|
상하좌우 네 방향으로만 이동할 수 있는 격자에서 사용한다.
가로 이동 거리와 세로 이동 거리를 더하여 목적지까지의 거리를 추정한다.
이 프로젝트에서는 4방향 이동을 사용하므로 Manhattan Distance를 적용한다.
Euclidean Distance
sqrt(dx² + dy²)
두 지점 사이의 직선거리를 계산한다.
대각선 이동이 가능한 환경에서 활용할 수 있다.
Chebyshev Distance
max(|dx|, |dy|)
가로, 세로, 대각선 방향으로 이동할 수 있는 8방향 격자에서 활용할 수 있다.
프로젝트의 Heuristic 구현
private int Heuristic(GraphNode a, GraphNode b)
{
int ax = a.id % graph.cols;
int ay = a.id / graph.cols;
int bx = b.id % graph.cols;
int by = b.id / graph.cols;
return Mathf.Abs(ax - bx) + Mathf.Abs(ay - by);
}
1차원 배열의 인덱스를 2차원 좌표로 변환한 다음 Manhattan Distance를 계산한다.
id % cols: 열 좌표를 구한다.id / cols: 행 좌표를 구한다.Mathf.Abs(): 두 좌표의 차이를 양수로 변환한다.
5. Dijkstra와 A*의 차이
두 알고리즘은 모두 우선순위 큐를 이용하여 최단 경로를 탐색할 수 있다.
가장 큰 차이는 우선순위 큐에 저장하는 우선순위 값이다.
Dijkstra
현재까지의 실제 이동 비용만 사용한다.
priority = newDistance
A*
현재까지의 실제 이동 비용과 목적지까지의 예상 비용을 더한다.
priority = newDistance + Heuristic(adjacent, goal)
즉, A*는 Dijkstra에 휴리스틱을 추가한 구조이다.
비교
| 구분 | Dijkstra | A* |
|---|---|---|
| 실제 이동 비용 | 사용 | 사용 |
| 예상 이동 비용 | 사용하지 않음 | 사용 |
| 우선순위 | g(n) | g(n) + h(n) |
| 탐색 방향 | 여러 방향으로 확장 | 목적지 방향으로 유도 |
| 최단 경로 | 보장 | 적절한 휴리스틱 조건에서 보장 |
6. 휴리스틱의 품질
A*의 탐색 효율은 휴리스틱이 얼마나 정확하게 목적지까지의 비용을 추정하는지에 따라 달라진다.
h(n) = 0
예상 비용을 사용하지 않는 경우이다.
f(n) = g(n)
따라서 Dijkstra와 동일한 방식으로 동작한다.
h(n)이 실제 최저 비용과 같은 경우
목적지까지의 비용을 정확하게 알고 있는 경우이다.
탐색 방향을 매우 효과적으로 유도할 수 있다.
h(n)이 실제 최저 비용보다 큰 경우
허용 가능한 휴리스틱 조건을 위반한다.
탐색은 더 빠르게 진행될 수도 있지만 최단 경로를 보장할 수 없다.
따라서 A*를 사용할 때는 탐색 속도뿐 아니라 최적 경로 보장 여부도 고려해야 한다.
7. Dijkstra와 A*의 시간 복잡도
우선순위 큐를 사용하는 일반적인 구현에서 두 알고리즘의 최악 시간 복잡도는 다음과 같이 표현할 수 있다.
O((V + E) log V)
다만 A*는 휴리스틱의 품질에 따라 실제 탐색하는 정점의 수가 달라진다.
좋은 휴리스틱을 사용하면 목적지와 관계없는 정점의 탐색을 줄일 수 있다.
따라서 실제 실행에서는 Dijkstra보다 빠르게 동작할 수 있지만 항상 더 빠른 것은 아니다.
8. 프로젝트의 실제 활용
이 프로젝트에서는 GraphSearch 클래스에서 Dijkstra와 A*를 구현한다.
Dijkstra
- 시작 정점의 거리를 0으로 초기화한다.
distances를 이용하여 현재까지의 최저 비용을 관리한다.- 우선순위 큐에는 실제 이동 비용을 저장한다.
- 인접 노드의
weight를 누적한다. previous를 기록하여 최종 경로를 복원한다.
A*
- Dijkstra와 동일하게 실제 이동 비용을 관리한다.
Heuristic()으로 목적지까지의 예상 비용을 계산한다.- 우선순위 큐에는 실제 비용과 예상 비용의 합을 저장한다.
- 목적지 방향으로 탐색을 유도한다.
previous를 이용하여 최종 경로를 복원한다.
9. 전체 구조 정리
가중치 그래프는 정점이나 간선마다 이동 비용을 부여한 그래프이다.
- Weighted Graph: 이동 비용을 고려하는 그래프이다.
- Dijkstra: 현재까지의 실제 이동 비용을 기준으로 최단 경로를 탐색한다.
- Priority Queue: 현재 비용이 가장 작은 정점을 먼저 처리한다.
- Distance: 시작점부터 현재 정점까지의 누적 비용이다.
- Previous: 경로 복원에 필요한 이전 정점 정보이다.
- A*: 실제 이동 비용과 예상 이동 비용을 함께 고려한다.
- Heuristic: 목적지까지의 예상 비용을 계산한다.
- Manhattan Distance: 4방향 격자에서 사용하는 거리 추정 방식이다.
핵심은 Dijkstra는 실제 이동 비용을 기준으로 탐색하고, A*는 여기에 목적지까지의 예상 비용을 추가하여 탐색 방향을 유도한다는 것이다.



