가중치 그래프와 최단 경로 알고리즘 (Dijkstra & A*) 정리

공재원
∙∙조회 7

가중치 그래프와 최단 경로 알고리즘 (Dijkstra & A*)

1. 가중치 그래프 (Weighted Graph)

일반적인 BFS는 모든 간선의 비용이 동일하다는 전제에서 최단 경로를 보장한다.

하지만 실제 문제에서는 이동하는 경로나 위치에 따라 비용이 달라지는 경우가 많다.

가중치가 필요한 이유

  • 지도에서 고속도로와 일반 도로는 이동 시간이 다르다.
  • 게임 맵에서 평지, 언덕, 장애물 주변의 이동 비용은 다를 수 있다.
  • 네트워크에서는 경로마다 전송 비용이나 지연 시간이 다를 수 있다.

이처럼 간선이나 이동에 비용을 부여한 그래프를 가중치 그래프라고 한다.

프로젝트의 가중치 표현

이 프로젝트에서는 GraphNode의 weight 필드를 이용하여 해당 노드로 이동하는 비용을 표현한다.

csharp
public class GraphNode
{
    public int weight = 1;
}

이 구조에서는 노드의 가중치를 해당 노드에 진입할 때 발생하는 비용으로 취급한다.

따라서 현재 노드에서 인접 노드로 이동할 때 인접 노드의 weight를 누적한다.

2. Dijkstra 알고리즘

Dijkstra(다익스트라) 알고리즘은 음수 가중치가 없는 그래프에서 시작 정점으로부터 다른 정점까지의 최단 경로를 구하는 알고리즘이다.

핵심 아이디어

현재까지 계산된 거리 중 가장 작은 값을 가진 미방문 정점을 선택하여 처리한다.

이러한 방식을 탐욕 선택(Greedy Selection)이라고 한다.

음수 가중치가 없다는 조건에서는 가장 가까운 정점의 최단 거리를 확정할 수 있다.

거리 초기화

알고리즘을 시작할 때 모든 정점까지의 거리를 초기화한다.

  • 시작 정점의 거리: 0
  • 나머지 정점의 거리: 무한대(∞)

시작 정점의 거리를 0으로 설정하는 이유는 시작 정점에서 다른 정점으로 이동할 때 발생하는 비용만 누적하기 위해서이다.

따라서 시작 정점 자체의 weight는 최초 이동 비용에 포함하지 않는다.

동작 과정

  1. 시작 정점의 거리를 0으로 설정한다.
  2. 시작 정점과 우선순위 0을 우선순위 큐에 추가한다.
  3. 우선순위 큐가 빌 때까지 반복한다.
  4. 큐에서 거리가 가장 작은 정점을 꺼낸다.
  5. 이미 방문한 정점이면 건너뛴다.
  6. 목적지에 도달했다면 탐색을 종료할 수 있다.
  7. 현재 정점과 연결된 인접 정점들을 확인한다.
  8. 현재 정점까지의 거리와 인접 정점의 이동 비용을 더한다.
  9. 새로 계산한 거리가 기존 거리보다 작으면 거리를 갱신한다.
  10. 이전 정점 정보를 기록하고 우선순위 큐에 추가한다.

거리 갱신 공식

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 구현

csharp
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에 휴리스틱을 추가한 구조이다.

비교

구분DijkstraA*
실제 이동 비용사용사용
예상 이동 비용사용하지 않음사용
우선순위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*는 여기에 목적지까지의 예상 비용을 추가하여 탐색 방향을 유도한다는 것이다.