C++ 최단 경로 알고리즘

개요 — 최단 경로 문제란 무엇인가

그래프에서 두 정점 사이의 최단 경로를 구하는 문제는 게임 AI 내비게이션, 네트워크 라우팅, 지도 앱 등 다양한 분야에서 사용됩니다.

게임 개발에서 최단 경로 알고리즘이 적용되는 대표적인 시나리오는 다음과 같습니다.

• AI 내비게이션: 캐릭터가 장애물을 피해 목적지까지 이동하는 최적 경로 계산
• 웨이포인트 시스템: 맵에 배치된 웨이포인트 그래프에서 두 지점 사이 최단 루트
• 자원 최적화: 전략 게임에서 물자를 가장 빠르게 운반할 경로 결정
• 스킬 트리 비용 계산: 특정 스킬에 도달하는 최소 포인트 경로

알고리즘마다 적용 조건이 다르므로 상황에 맞는 선택이 중요합니다.

알고리즘	간선 가중치	단일 출발	모든 쌍	시간 복잡도	비고
Dijkstra	양수만	O	X	O((V+E) log V)	실전 가장 많이 사용
Bellman-Ford	음수 가능	O	X	O(VE)	음수 사이클 탐지 가능
Floyd-Warshall	음수 가능	X	O	O(V³)	소규모 전체 쌍 탐색
A*	양수만	O	X	O(E log V) 이하	목표 지향, 게임 AI 최적

알고리즘 선택 원칙:

• 간선이 모두 양수이고 단일 출발점 → Dijkstra
• 게임 AI처럼 목표가 명확하고 휴리스틱을 정의할 수 있을 때 → A*
• 음수 간선이 있거나 음수 사이클 탐지가 필요할 때 → Bellman-Ford
• 모든 쌍의 최단 거리가 필요하고 정점 수가 적을 때(≤ 500) → Floyd-Warshall

---

Dijkstra 알고리즘

동작 원리

간선 가중치가 모두 양수일 때 단일 출발 최단 경로를 구합니다. 탐욕적(Greedy) 접근으로, 현재까지 발견된 가장 짧은 거리의 정점을 우선순위 큐(최소 힙)에서 꺼내 인접 정점의 거리를 **완화(Relaxation)**합니다.

초기: dist[src] = 0, 나머지 = INF
반복:
  1. 힙에서 dist가 가장 작은 (dist, u) 꺼내기
  2. 이미 처리된 정점이면 스킵
  3. u의 인접 v에 대해: dist[u] + w(u,v) < dist[v]이면 dist[v] 갱신 후 힙 삽입

핵심 특성:

• 음수 가중치가 있으면 동작하지 않음 (이미 처리된 정점의 거리가 더 줄어들 수 있어서)
• 우선순위 큐 사용 시 시간복잡도: O((V+E) log V)
• 가장 실용적이고 널리 사용되는 최단 경로 알고리즘

C++ 구현

#include <vector>
#include <queue>
#include <limits>

using Edge = std::pair<int, int>;  // {가중치, 목적지}
using Graph = std::vector<std::vector<Edge>>;

const int INF = std::numeric_limits<int>::max();

std::vector<int> Dijkstra(const Graph& graph, int src)
{
    int n = static_cast<int>(graph.size());
    std::vector<int> dist(n, INF);
    dist[src] = 0;

    // {거리, 정점}: 최소 힙
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;
    pq.push({0, src});

    while (!pq.empty())
    {
        auto [d, u] = pq.top();
        pq.pop();

        // 이미 더 짧은 경로로 처리된 정점은 스킵
        if (d > dist[u]) continue;

        for (auto [weight, v] : graph[u])
        {
            int newDist = dist[u] + weight;
            if (newDist < dist[v])
            {
                dist[v] = newDist;
                pq.push({newDist, v});
            }
        }
    }

    return dist;
}

경로 복원

std::vector<int> DijkstraWithPath(
    const Graph& graph, int src, int dst,
    std::vector<int>& path)
{
    int n = graph.size();
    std::vector<int> dist(n, INF);
    std::vector<int> prev(n, -1);  // 이전 정점 추적
    dist[src] = 0;

    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;
    pq.push({0, src});

    while (!pq.empty())
    {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (auto [weight, v] : graph[u])
        {
            if (dist[u] + weight < dist[v])
            {
                dist[v] = dist[u] + weight;
                prev[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    // 경로 복원
    for (int v = dst; v != -1; v = prev[v])
        path.push_back(v);
    std::reverse(path.begin(), path.end());

    return dist;
}

// 사용
Graph g(6);
// 간선 추가: g[u].push_back({weight, v})
g[0].push_back({4, 1});
g[0].push_back({2, 2});
g[1].push_back({1, 3});
g[2].push_back({5, 3});
g[2].push_back({3, 4});
g[3].push_back({7, 5});
g[4].push_back({2, 5});

std::vector<int> path;
auto dist = DijkstraWithPath(g, 0, 5, path);

// 경로 출력
for (int node : path)
    std::cout << node << " ";  // 0 → 2 → 4 → 5
std::cout << "\nDistance: " << dist[5] << "\n";  // 7

---

Bellman-Ford 알고리즘

동작 원리

음수 가중치 간선이 있어도 동작하며, 음수 사이클도 탐지할 수 있습니다. 모든 간선을 V-1번 반복하며 완화합니다. V-1번은 최단 경로에 포함될 수 있는 최대 간선 수이기 때문입니다.

초기: dist[src] = 0, 나머지 = INF
V-1회 반복:
  모든 간선 (u, v, w)에 대해:
    if dist[u] + w < dist[v]: dist[v] = dist[u] + w
V번째 반복에서 여전히 완화되면: 음수 사이클 존재

핵심 특성:

• 음수 간선 포함 그래프에서 사용 가능
• 음수 사이클 존재 여부 탐지 가능
• 시간복잡도 O(VE) — Dijkstra보다 느리지만 더 범용적
• 게임에서는 드물게 사용되나, 버프/디버프로 인한 음수 이동 비용 처리 시 유용

struct BFEdge { int from, to, weight; };

// {dist 배열, 음수 사이클 존재 여부}
std::pair<std::vector<int>, bool> BellmanFord(
    int n, const std::vector<BFEdge>& edges, int src)
{
    std::vector<int> dist(n, INF);
    dist[src] = 0;

    // V-1 번 완화 (Relaxation)
    for (int i = 0; i < n - 1; ++i)
    {
        for (const auto& e : edges)
        {
            if (dist[e.from] != INF &&
                dist[e.from] + e.weight < dist[e.to])
            {
                dist[e.to] = dist[e.from] + e.weight;
            }
        }
    }

    // V번째 반복: 완화가 일어나면 음수 사이클 존재
    bool hasNegCycle = false;
    for (const auto& e : edges)
    {
        if (dist[e.from] != INF &&
            dist[e.from] + e.weight < dist[e.to])
        {
            hasNegCycle = true;
            break;
        }
    }

    return {dist, hasNegCycle};
}

---

Floyd-Warshall 알고리즘

동작 원리

모든 정점 쌍 사이의 최단 경로를 O(V³)에 구합니다. 정점 수가 적을 때(≤ 500) 사용하며, 경유 정점 k를 하나씩 추가하면서 거리를 갱신하는 동적 프로그래밍 방식입니다.

점화식: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
k = 0 ~ V-1 순서로 반복 (k를 경유 정점으로 활용)

핵심 특성:

• 모든 쌍(All-Pairs) 최단 경로를 한 번에 계산
• 음수 간선 허용 (단, 음수 사이클 없어야 함)
• 시간복잡도 O(V³), 공간복잡도 O(V²)
• 구현이 단순하여 정점 수 적은 문제에 편리
• 게임에서는 정적 맵의 모든 웨이포인트 쌍 거리를 사전 계산할 때 활용

C++ 구현

const int INF = 1e9;

void FloydWarshall(std::vector<std::vector<int>>& dist)
{
    int n = dist.size();

    // k: 경유 정점
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);

    // 음수 사이클: dist[i][i] < 0
}

// 초기화
int n = 4;
std::vector<std::vector<int>> dist(n, std::vector<int>(n, INF));
for (int i = 0; i < n; ++i) dist[i][i] = 0;

// 간선 추가
dist[0][1] = 5; dist[0][2] = 4;
dist[1][2] = 2; dist[1][3] = 7;
dist[2][3] = 3;

FloydWarshall(dist);

std::cout << dist[0][3] << "\n";  // 0→2→3: 4+3=7

---

A* 알고리즘 (게임 AI)

동작 원리

Dijkstra에 휴리스틱(heuristic) 을 추가해 목표 방향으로 탐색을 유도합니다. 게임 내비게이션 메시에서 가장 많이 사용됩니다.

A*는 각 노드의 우선순위를 f(n) = g(n) + h(n)으로 평가합니다.

함수	의미
g(n)	시작점에서 현재 노드까지 실제 이동 비용
h(n)	현재 노드에서 목표까지 추정 비용 (휴리스틱)
f(n)	총 추정 비용 (낮을수록 먼저 탐색)

휴리스틱 선택:

• 맨해튼 거리: 격자 맵, 4방향 이동 시 |x1-x2| + |y1-y2|
• 유클리드 거리: 임의 방향 이동 시 sqrt((x1-x2)² + (y1-y2)²)
• 체비쇼프 거리: 8방향 이동 격자 맵 max(|x1-x2|, |y1-y2|)

허용 가능한 휴리스틱(Admissible Heuristic): 실제 비용을 절대 과대평가하지 않아야 A가 최적 경로를 보장합니다. 휴리스틱이 0이면 A는 Dijkstra와 동일하게 동작합니다.

핵심 특성:

• 목표가 명확하고 거리 휴리스틱을 정의할 수 있을 때 Dijkstra보다 훨씬 빠름
• 최악의 경우 O(E log V)이지만 좋은 휴리스틱을 쓰면 탐색 공간을 대폭 축소
• Unreal Engine의 UNavigationSystemV1이 내부적으로 NavMesh 위에서 A*를 사용

struct AStarNode
{
    int   id;
    float g;   // 출발점에서 현재 노드까지 실제 비용
    float h;   // 현재 노드에서 목표까지 추정 비용 (휴리스틱)
    float f() const { return g + h; }

    bool operator>(const AStarNode& other) const { return f() > other.f(); }
};

// 맨해튼 거리 휴리스틱 (격자 그래프)
float Heuristic(int from, int to, int cols)
{
    int fx = from % cols, fy = from / cols;
    int tx = to   % cols, ty = to   / cols;
    return static_cast<float>(std::abs(fx - tx) + std::abs(fy - ty));
}

std::vector<int> AStar(const Graph& graph, int src, int dst, int cols)
{
    int n = graph.size();
    std::vector<float> g(n, INF);
    std::vector<int>   prev(n, -1);
    g[src] = 0;

    std::priority_queue<AStarNode, std::vector<AStarNode>, std::greater<AStarNode>> open;
    open.push({src, 0.0f, Heuristic(src, dst, cols)});

    while (!open.empty())
    {
        auto [u, gu, hu] = open.top(); open.pop();

        if (u == dst) break;
        if (gu > g[u]) continue;  // 구식 노드 스킵

        for (auto [weight, v] : graph[u])
        {
            float ng = g[u] + weight;
            if (ng < g[v])
            {
                g[v]    = ng;
                prev[v] = u;
                open.push({v, ng, Heuristic(v, dst, cols)});
            }
        }
    }

    // 경로 복원
    std::vector<int> path;
    for (int v = dst; v != -1; v = prev[v])
        path.push_back(v);
    std::reverse(path.begin(), path.end());
    return path;
}

---

Unreal Engine 실전 활용

UNavigationSystemV1 — A* 기반 NavMesh 경로탐색

Unreal Engine의 NavigationSystem은 NavMesh 위에서 A* 알고리즘을 사용하여 경로를 탐색합니다.

#include "NavigationSystem.h"
#include "NavigationPath.h"

// 목적지까지의 경로를 동기적으로 탐색
void AMyAIController::RequestPathToDestination(const FVector& Destination)
{
    UNavigationSystemV1* NavSystem =
        UNavigationSystemV1::GetCurrent(GetWorld());
    if (!NavSystem) return;

    FNavPathSharedPtr NavPath;
    FPathFindingQuery Query(
        this,
        *NavSystem->GetDefaultNavDataInstance(),
        GetPawn()->GetActorLocation(),
        Destination
    );

    FPathFindingResult Result = NavSystem->FindPathSync(Query);
    if (Result.IsSuccessful())
    {
        // 경로 포인트 순회
        for (const FNavPathPoint& Point : Result.Path->GetPathPoints())
        {
            DrawDebugSphere(GetWorld(), Point.Location, 20.f, 8,
                FColor::Green, false, 3.f);
        }
    }
}

커스텀 웨이포인트 그래프에 Dijkstra 적용

NavMesh 없이 웨이포인트 그래프 기반 맵에서 Dijkstra로 최단 경로를 탐색하는 패턴입니다.

// 게임 시작 시 정적 맵의 모든 웨이포인트 쌍 거리를 Floyd-Warshall로 사전 계산
// → 런타임에는 O(1) 테이블 조회만 수행
UCLASS()
class UWaypointManager : public UGameInstanceSubsystem
{
    GENERATED_BODY()

public:
    // 초기화 시 Floyd-Warshall 실행 (정적 맵용)
    void Initialize(FSubsystemCollectionBase& Collection) override
    {
        BuildDistanceTable();
    }

    // 두 웨이포인트 사이의 사전 계산된 최단 거리 반환 — O(1)
    float GetPrecomputedDistance(int32 FromId, int32 ToId) const
    {
        if (PrecomputedDistances.Contains(TPair<int32,int32>(FromId, ToId)))
            return PrecomputedDistances[TPair<int32,int32>(FromId, ToId)];
        return TNumericLimits<float>::Max();
    }

private:
    // {WaypointFrom, WaypointTo} -> 최단 거리 캐시
    TMap<TPair<int32,int32>, float> PrecomputedDistances;

    void BuildDistanceTable()
    {
        // Floyd-Warshall로 모든 쌍 계산 후 PrecomputedDistances에 저장
        // 맵 로드 시 1회만 실행, 이후 런타임 탐색 비용 제거
    }
};

음수 가중치 처리 — 버프/디버프 적용 예시

Bellman-Ford는 게임에서 버프나 지형 효과로 인해 이동 비용이 음수가 될 수 있는 경우에 유용합니다.

// 예: 특정 지형은 이동을 가속시켜 "음수 비용" 효과
// 일반 구역: 비용 +5, 가속 지형: 비용 -2, 지뢰밭: 비용 +20
struct FTerrainEdge
{
    int32 From;
    int32 To;
    float MovementCost; // 음수 가능 (가속 구역)
};

// Bellman-Ford로 최소 비용 경로 탐색
std::pair<std::vector<float>, bool> FindPathWithBuffs(
    int32 NodeCount,
    const std::vector<FTerrainEdge>& Edges,
    int32 StartNode)
{
    std::vector<float> Dist(NodeCount, TNumericLimits<float>::Max());
    Dist[StartNode] = 0.f;

    for (int32 Iter = 0; Iter < NodeCount - 1; ++Iter)
    {
        for (const FTerrainEdge& E : Edges)
        {
            if (Dist[E.From] != TNumericLimits<float>::Max() &&
                Dist[E.From] + E.MovementCost < Dist[E.To])
            {
                Dist[E.To] = Dist[E.From] + E.MovementCost;
            }
        }
    }

    // 음수 사이클 탐지 (무한 가속 루프 방지)
    bool bHasNegCycle = false;
    for (const FTerrainEdge& E : Edges)
    {
        if (Dist[E.From] != TNumericLimits<float>::Max() &&
            Dist[E.From] + E.MovementCost < Dist[E.To])
        {
            bHasNegCycle = true;
            break;
        }
    }

    return {Dist, bHasNegCycle};
}

---

알고리즘 선택 가이드

간선 가중치가 모두 양수?
├── Yes: 단일 출발점만 필요?
│   ├── Yes: 목표 지점이 명확한가?
│   │   ├── Yes: A* (휴리스틱으로 탐색 범위 축소, 게임 AI 최적)
│   │   └── No: Dijkstra (출발점에서 모든 정점 최단 거리)
│   └── No: 모든 쌍 → Floyd-Warshall (V ≤ 500)
└── No: 음수 간선 포함
    ├── 음수 사이클 탐지 필요? → Bellman-Ford
    └── 모든 쌍 + 음수 포함 → Floyd-Warshall (음수 사이클 없을 때)

정적 맵 + 반복적 쿼리?
→ Floyd-Warshall로 사전 계산 후 테이블 캐싱 → 런타임 O(1)

---

정리

알고리즘	핵심 자료구조	시간복잡도	특징	게임 활용
Dijkstra	우선순위 큐(Min-Heap)	O((V+E) log V)	양수 가중치 필수, 빠름	웨이포인트 탐색
A*	우선순위 큐 + 휴리스틱	O(E log V) 이하	목표 지향, 실용적으로 가장 빠름	NavMesh, 타일맵 AI
Bellman-Ford	엣지 리스트	O(VE)	음수 가중치·사이클 처리	버프/디버프 비용 맵
Floyd-Warshall	2D 거리 배열	O(V³)	모든 쌍, 구현 단순	사전 계산 거리 테이블

게임 실전에서는 Dijkstra와 A*가 가장 자주 사용됩니다. 정적 맵에서는 Floyd-Warshall로 사전 계산된 결과를 캐싱해 런타임 비용을 제거할 수 있으며, 음수 이동 비용(버프·가속 지형)이 등장하는 시스템에서는 Bellman-Ford가 안전한 선택입니다.

자주 하는 실수와 주의사항

// 주의 1: Dijkstra에서 음수 가중치 사용 — 잘못된 결과 발생
// 음수 간선이 있으면 Bellman-Ford 또는 Johnson 알고리즘 사용

// 주의 2: Floyd-Warshall 초기화 — 자기 자신 거리는 0
for (int i = 0; i < n; ++i) dist[i][i] = 0; // 반드시 0으로 초기화

// 주의 3: A* 휴리스틱 과대평가 — 최적 경로 보장 불가
// 허용 가능한 휴리스틱(h(n) <= 실제 거리)만 최적 보장

// 주의 4: Dijkstra에서 중복 노드 스킵 누락
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // 이 줄 없으면 성능 저하 및 오류 가능