C++ 최단 경로 알고리즘

최단 경로 문제

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

알고리즘	간선 가중치	단일 출발	모든 쌍	시간 복잡도
Dijkstra	양수만	O	X	O((V+E) log V)
Bellman-Ford	음수 가능	O	X	O(VE)
Floyd-Warshall	음수 가능	X	O	O(V³)

---

Dijkstra 알고리즘

간선 가중치가 모두 양수일 때 단일 출발 최단 경로를 구합니다. 우선순위 큐를 사용합니다.

#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 알고리즘

음수 가중치 간선이 있을 때 사용합니다. 음수 사이클도 탐지할 수 있습니다.

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) 사용합니다.

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)을 추가해 목표 방향으로 탐색을 유도합니다. 게임 내비게이션 메시에서 가장 많이 사용됩니다.

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;
}

---

알고리즘 선택 가이드

간선 가중치가 모두 양수?
├── Yes: 단일 출발점만 필요?
│   ├── Yes: Dijkstra (우선순위 큐, O((V+E) log V))
│   │        게임 AI라면 A* (목표 지향 탐색)
│   └── No: 모든 쌍 → Floyd-Warshall
└── No: 음수 간선 포함
    ├── 음수 사이클 탐지 필요? → Bellman-Ford
    └── 모든 쌍 → Floyd-Warshall (음수 사이클 없을 때)

---

정리

알고리즘	핵심 자료구조	특징
Dijkstra	우선순위 큐	양수 가중치, 빠름
A*	우선순위 큐 + 휴리스틱	게임 내비게이션
Bellman-Ford	엣지 리스트	음수 가중치, 음수 사이클 탐지
Floyd-Warshall	2D 배열	모든 쌍, 구현 단순

게임에서는 Dijkstra와 A*가 가장 자주 사용됩니다. 정적 맵에서는 사전 계산된 Floyd-Warshall 결과를 캐싱해 런타임 비용을 제거하기도 합니다.