Shortest path problem

Computer Science Jun 25, 2025

Introduction

Shortest path problem이란 무엇일까. 한글로 직역하면 최단거리 알고리즘이 되는 이 알고리즘은 이름 그대로 어떤 그래프에서 위치간의 최단 거리를 찾는 알고리즘이다. 말만 들어서는 체감하기 힘들지만, 최단거리 알고리즘은 우리의 내비게이션부터 네트워크 시스템, 물류 배송 등 여러 분야에서 이미 빠질 수 없는 필수 기술로 자리잡았다.

하지만 그렇다고 해서 최선의 최단거리 알고리즘을 구현하는 해법이 확정적으로 존재하는 것은 아니다. 세상에는 여러가지 최단거리 알고리즘이 존재하고, 각각은 목표로 하는것이 다르며, 이에 따른 장단점 또한 차이난다. 이번 글에서는 PS에서 사용되는 4대 최단거리 알고리즘에 대하여 알아보고자 한다.

서론이 길었다. 시작하자.

BFS Pathfinding

BFS는 사실은 최단거리 알고리즘이 아니라 그래프 탐색 알고리즘이다. 하지만 DFS와는 다르게 starting node로 부터 layer별로 탐색해 나가는 것이 무가중치 그래프, 혹은 그래프의 모든 간선의 가중치가 전부 같은 그래프를 탐색할때 사용하기 좋은 알고리즘이 되었다.

BFS를 대부분의 독자들은 알 것 같지만, 간단하게 설명하자면, 그래프 탐색 알고리즘의 일종이다. 작동 원리는 다음과 같다 :

Queue에 시작 Note를 추가한다.
Queue가 빌 때까지 반복한다.
- Queue 가장 앞 원소를 제거하여 연결된 모든 점들을 탐색한다.
- 방문 안한 점이 있다면, 방문하였다 표시 후 Queue에 추가한다.

이게 끝이다. 이 알고리즘을 이용하면 매우 간단하게 그래프 전체를 탐색할 수 있다.

자, 여기서 한가지 특징에 주목하자. 어떤 점에 대하여 시작점으로부터의 거리 d또한 같이 생각해보자. Queue에서 제거되는 순서대로 본다면, 어떤 거리 \(n\)이 완전히 처리되어야지만 거리 \(n+1\)이 처리되기 시작한다. 만일 이런 상황에서 우리가 종료점에 도착하자마자 프로세스를 종료한다면, 그것은 곧 종료점으로 가는 최단거리일 것이다.

여러가지 특징들

Time Complexity : \(O(V + E)\)
장점 :
- 로직이 매우 간단하다.
- 그래프 크기가 커짐에 따라 시간복잡도가 선형적으로 증가한다.
단점
- 오직 같은 가중치를 가진 그래프에서만 작동한다.

#include <bits/stdc++.h>
using namespace std;

vector<int> bfsShortestPath(int numVertices, int start,
                            const vector<vector<int>>& adjList) {
    const int INF = INT_MAX;
    vector<int> distance(numVertices, INF);
    queue<int> q;

    distance[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adjList[u]) {
            if (distance[v] == INF) {
                distance[v] = distance[u] + 1;
                q.push(v);
            }
        }
    }

    return distance;
}

int main() {
    int V = 5;
    int source = 0;
    
    vector<vector<int>> unweightedAdj = {
        {1, 2},    // 0
        {0, 2, 3}, // 1
        {0, 1, 3}, // 2
        {1, 2, 4}, // 3
        {3}        // 4
    };
    auto bfsDist = bfsShortestPath(V, source, unweightedAdj);
    cout << "BFS distances from " << source << ":\n";
    for (int i = 0; i < V; ++i)
        cout << "  to " << i << ": "
             << (bfsDist[i] == INT_MAX ? -1 : bfsDist[i]) << "\n";
    return 0;
}

Dijkstra's Algorithm

다익스트라 알고리즘(부르는 사람에 따라서 데이크스트라 알고리즘이라고도 한다)은 한 점에서 나머지 모든 점으로의 거리를 구하는데 최적화되어있는 알고리즘이다. 이 알고리즘은 에츠허르 다익스트라라는 컴퓨터 과학자가 1956년에 고안해낸 것이다.

작동 원리는 생각보다 BFS와 비슷하고, 실제로 외우기 쉽게 하기 위하여 BFS와 최대한 유사한 형식을 일부로 지켜 코딩하는 사람들도 있다.

다익스트라의 작동구조는 다음과 같다 :

시작점으로부터 갈 수 있는 모든 점들을 Priority Queue에 집어넣는다.
Queue가 빌 때까지 반복한다.
- 현재까지의 거리가 최소인 지점을 Priority Queue에서 꺼낸다.
- 거기서 갈 수 있는 점들을 모두 탐색하며, 이때 현재 확인 중인 점을 통과하여 가는 것이 그 점에 기록되어있는 최소보다 작을 경우, 최소를 업데이트 후 그 점을 Queue에 집어넣는다.

이 알고리즘은 뼈대부터가 BFS와 매우 비슷해 보인다. 하지만 단순한 Queue를 사용하여 무가중치 그래프만을 탐색 할 수 있었던 점을 Priority Queue를 사용하여 해결하였다.

여러가지 특징들

Time Complexity : \(O((V+E)log V)\)
장점 :
- 방향성이 상관이 없다. 그래프가 무방향인지 단방향인지에 상관없이 최단 거리를 구하는데 이용할 수 있다.
- 최단 거리 뿐만 아니라, 실제 최단 경로를 구할때 사용 가능하다.
단점
- "음수" 가중치를 해결하지 못한다. 즉 어떤 간선을 통해 전체 비용이 감소하는 경우, 이 알고리즘을 사용하지 못한다.

#include <bits/stdc++.h>
using namespace std;

vector<int> dijkstraShortestPath(int numVertices, int start,
                                 const vector<vector<pair<int,int>>>& adjList) {
    const int INF = INT_MAX;
    vector<int> distance(numVertices, INF);
    distance[start] = 0;

    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<pair<int,int>>> q;
    q.push({0, start});

    while (!q.empty()) {
        auto [distU, u] = q.top(); 
        q.pop();
        if (distU > distance[u]) continue;

        for (auto [v, weight] : adjList[u]) {
            int cand = distU + weight;
            if (cand < distance[v]) {
                distance[v] = cand;
                q.push({cand, v});
            }
        }
    }

    return distance;
}

int main() {
    int V = 5;
    int source = 0;
    vector<vector<pair<int,int>>> weightedAdj(V);
    weightedAdj[0] = {{1, 5}, {2, 3}};
    weightedAdj[1] = {{2, 2}, {3, 6}};
    weightedAdj[2] = {{1, 1}, {3, 4}, {4, 2}};
    weightedAdj[3] = {{4, 1}};
    auto dijkstraDist = dijkstraShortestPath(V, source, weightedAdj);
    cout << "\nDijkstra distances from " << source << ":\n";
    for (int i = 0; i < V; ++i)
        cout << "  to " << i << ": "
             << (dijkstraDist[i] == INT_MAX ? -1 : dijkstraDist[i]) << "\n";

    return 0;
}

Bellman-Ford Algorithm

벨만 포드 알고리즘은 한 시작 노드에 대하여 나머지 노드로의 최단 거리를 구하는 알고리즘이다. 시간 복잡도는 앞선 두개에 비해 꽤 느리다. 그럼 도대체 다익스트라를 놔두고 이건 왜 쓰는걸까? 그건 바로 음수 가중치를 처리할 수 있는 능력 때문이다.

벨만 포드의 알고리즘은 다음과 같이 작동한다 :

거리 테이블을 준비한다.
아래 과정을 (정점 - 1)번 반복한다.
- 모든 간선에 대하여, 그것을 통과하였을떄의 새로운 최소비용을 생각하며 대상 노드에 기록한다.
만일 이 모든 과정이 끝나고 기록 갱신을 한번 더 시도했을때 최단거리가 다시 업데이트 된다면, 그것은 음수 사이클이 존재한다는 이야기로, \(-\infty\)가 정답이다.

이 알고리즘은 워낙 특이하니, 왜 이 알고리즘이 음수 가중치를 처리할 수 있고, 음수 사이클을 판별할 수 있는지 알아보자.

일단 다익스트라가 왜 음수 가중치를 처리 못하는지는 간단하다. 다익스트라를 가능하게 하는 기본 정리가 바로 Queue에서 뽑는 거리는 항상 확정된 최단 거리 뿐이라는 것이다. 아직 어떤 점 \(P\)를 방문하지 않은 상태에서, 원래의 다익스트라라면 \(P\)로 가는 모든 경로들이 Queue에 Push되어 있을거고, 그중에서 최소를 찾아 사용할 것이다. 하지만, 음수 가중치가 추가되게 된다면, 한 점을 여러번 방문하는 일이 생겨 더 이상 우리가 알던 다익스트라가 아니게 된다.

하지만, 벨만 포드는 모든 간선을 매순간 확인하므로 항상 음수 가중치를 확인 가능하다.

그렇다면 벨만 포드는 어떻게 작동하는 것일까? 정점 - 1은 어디서 나온 것이고, 음수 사이클은 어떻게 찾을까?

생각해보자. 만일 \(V\)개의 점들이 일직선으로 연결되어 있을 경우, 최단 거리는 모르겠지만 일단 경로는 \(V-1\)개의 간선을 지날 것이다. 한번 전체 업데이트를 하면 시작점으로부터 한단계 진행하므로, \(V-1\)번을 하면 (이론상) 최종적인 최단경로를 구할 수 있는 것이다.

하지만 예외는 존재한다. 만일 (-1, -3, 3)이 사이클로 연결되어 있다 생각하자. 이 사이클을 1바퀴 돌때마다 비용이 1씩 감소한다. 그렇다면, 비용은 \(-\infty\)아닌가? 이것은 어떻게 해야 할까?

만일 음수 사이클이 존재한다면, \(V-1\)번의 시행 이후에도 최솟값이 계속 업데이트 되어야 할것이다(없다면 변화가 없을 것이다). 따라서 반복문 내부의 과정을 한번 더 돌려 변화가 있는지 관찰하면 되는 것이다.

여러가지 특징들

Time Complexity : \(O(VE)\)
장점 :
- 음수 가중치 처리가 가능하다.
단점
- 시간복잡도가 크다. 모든 간선들을 업데이트 하기 때문에 비효율적이다.

#include <bits/stdc++.h>
using namespace std;

vector<int> bellmanFordShortestPath(int numVertices, int start,
                                    const vector<tuple<int,int,int>>& edgeList) {
    const int INF = INT_MAX;
    vector<int> distance(numVertices, INF);
    distance[start] = 0;

    for (int i = 1; i < numVertices; ++i) {
        bool anyUpdate = false;
        for (auto& [u, v, w] : edgeList) {
            if (distance[u] != INF && distance[u] + w < distance[v]) {
                distance[v] = distance[u] + w;
                anyUpdate = true;
            }
        }
        if (!anyUpdate) break;
    }

    for (auto& [u, v, w] : edgeList) {
        if (distance[u] != INF && distance[u] + w < distance[v]) {
            throw runtime_error("Negative-weight cycle detected");
        }
    }

    return distance;
}


int main() {
    int V = 5;
    int source = 0;
    
    vector<tuple<int,int,int>> edgeList = {
        {0,1,5}, {0,2,3}, {1,2,2}, {1,3,6},
        {2,1,1}, {2,3,4}, {2,4,2}, {3,4,1}
    };
    
    try {
        auto bfDist = bellmanFordShortestPath(V, source, edgeList);
        cout << "\nBellman-Ford distances from " << source << ":\n";
        for (int i = 0; i < V; ++i)
            cout << "  to " << i << ": "
                 << (bfDist[i] == INT_MAX ? -1 : bfDist[i]) << "\n";
    } catch (const exception& e) {
        cout << "\nBellman-Ford error: " << e.what() << "\n";
    }
    return 0;
}

Floyd-Warshall Algorithm

마지막 알고리즘인 플로이드-와샬 알고리즘은 단순하면서도 강력하다. 이는 말그대로 모든 점으로부터 모든 점까지의 최단 거리를 동시에, 전부 계산 가능하다. 또한 Dynamic Programming을 활용하면서도 나름 간단하계 설계가 되어있어 구현하기도 매우 직관적이다.

여러가지 특징들

Time Complexity : \(O(V^3)\)
장점 :
- 구현이 매우 쉽다
- 직관적이다.
단점
- 시간복잡도가 크다. 장난아니게 크다. 어느정도냐면, \(V > 500\)정도에서는 사용이 아예 불가능한 알고리즘이다.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> floydWarshall(int numVertices,
                                  const vector<vector<int>>& adjMatrix) {
    const int INF = 1e9;
    // copy initial matrix
    vector<vector<int>> dist = adjMatrix;

    for (int k = 0; k < numVertices; ++k) {
        for (int i = 0; i < numVertices; ++i) {
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < numVertices; ++j) {
                if (dist[k][j] == INF) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    return dist;
}

int main() {
    int V = 5;
    int source = 0;

    const int INF = 1e9;
    vector<vector<int>> adjMatrix(V, vector<int>(V, INF));
    for (int i = 0; i < V; ++i) adjMatrix[i][i] = 0;
    for (auto& [u, v, w] : edgeList) {
        adjMatrix[u][v] = w;
    }

    auto allPairs = floydWarshall(V, adjMatrix);
    cout << "\nFloyd-Warshall all-pairs distances:\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            int d = allPairs[i][j];
            cout << (d == INF ? -1 : d) << (j+1 < V ? ' ' : '\n');
        }
    }

    return 0;
}

Conclusion

이것으로 PS 문제들에서 사용되는 유명한 최단경로 알고리즘 4가지를 알아보았다. 각각이 필요한 곳은 천차만별로, 문제의 상황을 정확이 인식하고 필요한 알고리즘을 사용하는 능력이 필요하다. 개인적으로는 위에서 소개한 문제들은 각 알고리즘에 대한 매우 좋은 입문이여서 전부 풀어보는 것을 추천한다. 혹시 이 글에 나온 문제들에 대한 정답 코드가 궁금하다면 여기를 참고바란다.

Recommended for you

Series : SOLAR SYSTEM

시리즈 | The Solar System - 2. Mercury

a day ago • 10 min read

Arts & Music

드럼스틱

3 days ago • 7 min read

Technology

INS(Inertial Navigation System)

4 days ago • 19 min read

순열, 반전수, 홀짝성

시리즈 | The Solar System - 2. Mercury

The Complement System

드럼스틱

Shortest path problem

Introduction

BFS Pathfinding

여러가지 특징들

관련 문제

Dijkstra's Algorithm

여러가지 특징들

관련 문제

Bellman-Ford Algorithm

여러가지 특징들

관련 문제

Floyd-Warshall Algorithm

여러가지 특징들

관련 문제

Conclusion

Tags

Lee Sihoo

Recommended for you

시리즈 | The Solar System - 2. Mercury

드럼스틱

INS(Inertial Navigation System)

순열, 반전수, 홀짝성

시리즈 | The Solar System - 2. Mercury

The Complement System

드럼스틱

Introduction

BFS Pathfinding

여러가지 특징들

관련 문제

Dijkstra's Algorithm

여러가지 특징들

관련 문제

Bellman-Ford Algorithm

여러가지 특징들

관련 문제

Floyd-Warshall Algorithm

여러가지 특징들

관련 문제

Conclusion

Tags

Subscribe to our newsletter

Lee Sihoo

Recommended for you

시리즈 | The Solar System - 2. Mercury

드럼스틱

INS(Inertial Navigation System)