최단 경로 알고리즘 선택 관점

최단 경로는 하나의 알고리즘으로 끝나지 않습니다. 음수 간선이 있는지, 시작점이 하나인지 여러 개인지에 따라 정답 알고리즘이 달라집니다. 그래서 구현보다 우선 입력 조건을 읽고 도구를 고르는 습관이 중요합니다.

Dijkstra를 만능처럼 적용하면 음수 간선에서 오답이 나기 쉽습니다. 여기서는 Dijkstra, Bellman-Ford, Floyd-Warshall을 외우는 방식이 아니라 어떤 조건이면 무엇을 써야 하는지를 선택 흐름으로 정리합니다.

최단 경로 알고리즘 선택 흐름도: 입력 조건에 따라 Dijkstra, Bellman-Ford, Floyd-Warshall을 고르는 기준

핵심 개념: 최단 경로 알고리즘 선택

최단 경로 문제는 코드보다 입력 조건을 우선 읽어야 정답 알고리즘을 고를 수 있습니다. 문제를 받으면 음수 간선이 있는지부터 체크하고 시작하세요.

Dijkstra는 음수 간선이 없는 단일 시작점 최단 거리 문제의 기본 도구입니다. 우선순위 큐로 현재 최단 거리를 가진 정점을 확정해 나가며 O((V+E)logV)로 동작합니다. 버스 요금처럼 간선 가중치가 모두 0 이상이면 시작점에서 각 정점까지 거리를 빠르게 계산할 수 있습니다.

Bellman-Ford는 음수 간선이 있는 그래프에서도 안전하게 동작합니다. 간선 완화를 V-1번 반복해 최단 거리를 구하고, 추가 완화로 음수 사이클 여부도 검사합니다. 할인 쿠폰처럼 음수 비용이 포함된 모델에서는 Dijkstra 대신 Bellman-Ford를 선택해야 오답을 피할 수 있습니다.

Floyd-Warshall는 모든 정점 쌍의 최단 거리가 필요할 때 쓰는 알고리즘입니다. 중간 정점 집합을 단계적으로 확장하는 DP로 O(V^3)에 전체 쌍 거리를 계산합니다. 정점 수가 비교적 작고 모든 도시 쌍 질의가 필요한 경우 구현이 단순하고 일관성이 좋습니다.

최단 경로 전략이 실무에서 중요한 이유

조건에 맞지 않는 알고리즘을 쓰면 정답이 틀리거나 시간 제한을 넘깁니다.
예를 들어 음수 간선이 있는 그래프에 Dijkstra를 적용하면 잘못된 거리 확정이 발생할 수 있습니다.

또한 모든 쌍 최단 경로가 필요한데 단일 소스 알고리즘을 반복하면 비효율이 큽니다.
문제 요구 범위를 우선 고정하는 것이 핵심입니다.

음수 간선 오답 재현으로 검증하기

오답 -> 디버깅 -> 교정 -> 검증 순서를 먼저 고정하고 예제를 따라가면 경계 버그를 빠르게 줄일 수 있습니다.

최단 경로 알고리즘 선택을 입력 조건으로 우선 결정해 봅니다.

조건 A: 음수 간선 없음, 시작점 1개
조건 B: 음수 간선 있음, 음수 사이클 여부 확인 필요
조건 C: 모든 정점 쌍 거리 필요

A는 Dijkstra가 기본입니다.
B는 Bellman-Ford를 사용합니다.
C는 Floyd-Warshall 또는 다중 소스 전략을 검토합니다.

최단 경로: Dijkstra (음수 간선 없음)

문제 의도: 음수 간선이 없는 그래프에서 Dijkstra 기본 흐름을 확인합니다.
입력 예시: n=4, 가중치 간선 목록, 시작 정점 1
출력 예시: 시작점에서 각 정점까지 거리 배열

main.cpp

#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

vector<long long> dijkstra(const vector<vector<pair<int, int>>>& graph, int start) {
    int n = static_cast<int>(graph.size()) - 1;
    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        pair<long long, int> curItem = pq.top();
        pq.pop();
        long long curDist = curItem.first;
        int cur = curItem.second;
        if (curDist > dist[cur]) continue;
        for (const auto& edge : graph[cur]) {
            int nxt = edge.first;
            int w = edge.second;
            long long cand = curDist + w;
            if (cand < dist[nxt]) {
                dist[nxt] = cand;
                pq.push({cand, nxt});
            }
        }
    }
    return dist;
}

int main() {
    int n = 4;
    vector<vector<pair<int, int>>> g(n + 1);
    vector<tuple<int, int, int>> edges = {
        {1, 2, 2}, {1, 3, 5}, {2, 3, 1}, {2, 4, 2}, {3, 4, 3}
    };
    for (const auto& edge : edges) {
        int u = get<0>(edge);
        int v = get<1>(edge);
        int w = get<2>(edge);
        g[u].push_back({v, w});
    }

    auto dist = dijkstra(g, 1);
    for (int i = 1; i <= 4; ++i) cout << dist[i] << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static long[] dijkstra(List<List<int[]>> graph, int start) {
        int n = graph.size() - 1;
        long INF = Long.MAX_VALUE / 4;
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        PriorityQueue<long[]> pq = new PriorityQueue<>(
            new Comparator<long[]>() {
                @Override
                public int compare(long[] a, long[] b) {
                    return Long.compare(a[0], b[0]);
                }
            }
        );
        dist[start] = 0;
        pq.offer(new long[]{0, start});

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long curDist = cur[0];
            int node = (int) cur[1];
            if (curDist > dist[node]) continue;
            for (int[] edge : graph.get(node)) {
                int nxt = edge[0], w = edge[1];
                long cand = curDist + w;
                if (cand < dist[nxt]) {
                    dist[nxt] = cand;
                    pq.offer(new long[]{cand, nxt});
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int n = 4;
        List<List<int[]>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());

        int[][] edges = {
            {1, 2, 2}, {1, 3, 5}, {2, 3, 1}, {2, 4, 2}, {3, 4, 3}
        };
        for (int[] e : edges) g.get(e[0]).add(new int[]{e[1], e[2]});

        long[] dist = dijkstra(g, 1);
        System.out.println(Arrays.toString(Arrays.copyOfRange(dist, 1, 5)));
    }
}

main.py

import heapq

def dijkstra(graph, start):
    n = len(graph) - 1
    INF = 10**18
    dist = [INF] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        cur_dist, cur = heapq.heappop(pq)
        if cur_dist > dist[cur]:
            continue

        for nxt, w in graph[cur]:
            cand = cur_dist + w
            if cand < dist[nxt]:
                dist[nxt] = cand
                heapq.heappush(pq, (cand, nxt))

    return dist

n = 4
g = [[] for _ in range(n + 1)]
edges = [(1, 2, 2), (1, 3, 5), (2, 3, 1), (2, 4, 2), (3, 4, 3)]
for u, v, w in edges:
    g[u].append((v, w))

print(dijkstra(g, 1)[1:])  # [0, 2, 3, 4]

main.rs

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn dijkstra(graph: &[Vec<(usize, i64)>], start: usize) -> Vec<i64> {
    let n = graph.len() - 1;
    let inf = i64::MAX / 4;
    let mut dist = vec![inf; n + 1];
    let mut pq = BinaryHeap::<Reverse<(i64, usize)>>::new();
    dist[start] = 0;
    pq.push(Reverse((0, start)));

    while let Some(Reverse((cur_dist, cur))) = pq.pop() {
        if cur_dist > dist[cur] {
            continue;
        }
        for &(nxt, w) in &graph[cur] {
            let cand = cur_dist + w;
            if cand < dist[nxt] {
                dist[nxt] = cand;
                pq.push(Reverse((cand, nxt)));
            }
        }
    }
    dist
}

fn main() {
    let n = 4usize;
    let mut g = vec![Vec::<(usize, i64)>::new(); n + 1];
    let edges = vec![(1usize, 2usize, 2i64), (1, 3, 5), (2, 3, 1), (2, 4, 2), (3, 4, 3)];
    for (u, v, w) in edges {
        g[u].push((v, w));
    }
    let dist = dijkstra(&g, 1);
    println!("{:?}", &dist[1..=4]);
}

최단 경로 동작 초기 거리값 검토

우선순위 큐에서 꺼낸 거리가 최신 거리보다 크면 stale 상태로 건너뜁니다.
이 최적화는 실무 구현에서 필수입니다.
음수 간선이 없다면 Dijkstra는 빠르고 안정적인 기본 선택입니다.

평균 시간복잡도: O((V+E) log V)
최악 시간복잡도: O((V+E) log V)
공간복잡도: O(V+E)

최단 경로: Bellman-Ford (음수 간선 대응)

문제 의도: 음수 가중치가 있는 경우의 최단 거리와 음수 사이클 검출을 수행합니다.
입력 예시: edges=[(1,2,4),(2,3,-2), ...], start=1
출력 예시: 거리 배열 또는 음수 사이클 감지 결과

main.cpp

#include <iostream>
#include <limits>
#include <optional>
#include <tuple>
#include <vector>
using namespace std;

optional<vector<long long>> bellmanFord(int n, const vector<tuple<int, int, int>>& edges, int start) {
    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n + 1, INF);
    dist[start] = 0;

    for (int i = 0; i < n - 1; ++i) {
        bool updated = false;
        for (const auto& edge : edges) {
            int u = get<0>(edge);
            int v = get<1>(edge);
            int w = get<2>(edge);
            if (dist[u] == INF) continue;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;
    }

    for (const auto& edge : edges) {
        int u = get<0>(edge);
        int v = get<1>(edge);
        int w = get<2>(edge);
        if (dist[u] != INF && dist[u] + w < dist[v]) return nullopt;
    }
    return dist;
}

int main() {
    vector<tuple<int, int, int>> edges = {{1, 2, 4}, {1, 3, 5}, {2, 3, -2}, {3, 4, 3}};
    auto res = bellmanFord(4, edges, 1);
    if (!res) {
        cout << "negative cycle\n";
    } else {
        for (int i = 1; i <= 4; ++i) cout << (*res)[i] << " ";
        cout << "\n";
    }
    return 0;
}

Main.java

import java.util.Arrays;

public class Main {
    static long[] bellmanFord(int n, int[][] edges, int start) {
        long INF = Long.MAX_VALUE / 4;
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        for (int i = 0; i < n - 1; i++) {
            boolean updated = false;
            for (int[] e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] == INF) continue;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }
            if (!updated) break;
        }

        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INF && dist[u] + w < dist[v]) return null;
        }
        return dist;
    }

    public static void main(String[] args) {
        int[][] edges = {{1,2,4}, {1,3,5}, {2,3,-2}, {3,4,3}};
        long[] dist = bellmanFord(4, edges, 1);
        System.out.println(Arrays.toString(Arrays.copyOfRange(dist, 1, 5)));
    }
}

main.py

def bellman_ford(n, edges, start):
    INF = 10**18
    dist = [INF] * (n + 1)
    dist[start] = 0

    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] == INF:
                continue
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break

    # 음수 사이클 검사
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None  # negative cycle

    return dist

edges = [(1,2,4), (1,3,5), (2,3,-2), (3,4,3)]
print(bellman_ford(4, edges, 1)[1:])  # [0, 4, 2, 5]

main.rs

fn bellman_ford(n: usize, edges: &[(usize, usize, i64)], start: usize) -> Option<Vec<i64>> {
    let inf = i64::MAX / 4;
    let mut dist = vec![inf; n + 1];
    dist[start] = 0;

    for _ in 0..(n - 1) {
        let mut updated = false;
        for &(u, v, w) in edges {
            if dist[u] == inf {
                continue;
            }
            if dist[u] + w < dist[v] {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if !updated {
            break;
        }
    }

    for &(u, v, w) in edges {
        if dist[u] != inf && dist[u] + w < dist[v] {
            return None;
        }
    }
    Some(dist)
}

fn main() {
    let edges = vec![(1, 2, 4), (1, 3, 5), (2, 3, -2), (3, 4, 3)];
    if let Some(dist) = bellman_ford(4, &edges, 1) {
        println!("{:?}", &dist[1..=4]);
    } else {
        println!("negative cycle");
    }
}

최단 경로 동작 완화 단계 추적

Bellman-Ford는 간선을 반복 완화(relaxation)해 최단 거리를 갱신합니다.
음수 사이클이 있으면 추가 완화가 가능하다는 성질로 탐지할 수 있습니다.
속도는 느리지만 음수 간선이 있는 문제에서 신뢰할 수 있는 선택입니다.

평균 시간복잡도: O(VE)
최악 시간복잡도: O(VE)
공간복잡도: O(V)

최단 경로: Floyd-Warshall (모든 쌍)

문제 의도: 모든 정점 쌍 최단 거리를 행렬 기반으로 한 번에 계산합니다.
입력 예시: 인접 행렬 mat
출력 예시: 갱신된 최단 거리 행렬

main.cpp

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> floydWarshall(const vector<vector<int>>& mat) {
    int n = (int)mat.size();
    vector<vector<int>> dist = mat;
    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] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    return dist;
}

int main() {
    const int INF = 1'000'000'000;
    vector<vector<int>> mat = {
        {0, 3, INF, 7},
        {8, 0, 2, INF},
        {5, INF, 0, 1},
        {2, INF, INF, 0}
    };
    cout << floydWarshall(mat)[0][2] << "\n";
    return 0;
}

Main.java

public class Main {
    static int[][] floydWarshall(int[][] mat) {
        int n = mat.length;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            System.arraycopy(mat[i], 0, dist[i], 0, n);
        }

        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] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int INF = 1_000_000_000;
        int[][] mat = {
            {0, 3, INF, 7},
            {8, 0, 2, INF},
            {5, INF, 0, 1},
            {2, INF, INF, 0}
        };
        System.out.println(floydWarshall(mat)[0][2]);
    }
}

main.py

def floyd_warshall(mat):
    n = len(mat)
    dist = [row[:] for row in mat]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

INF = 10**9
mat = [
    [0,   3, INF, 7],
    [8,   0,   2, INF],
    [5, INF,   0, 1],
    [2, INF, INF, 0],
]
print(floyd_warshall(mat)[0][2])  # 5

main.rs

fn floyd_warshall(mat: &[Vec<i32>]) -> Vec<Vec<i32>> {
    let n = mat.len();
    let mut dist = mat.to_vec();

    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                if dist[i][k] + dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    dist
}

fn main() {
    let inf = 1_000_000_000;
    let mat = vec![
        vec![0, 3, inf, 7],
        vec![8, 0, 2, inf],
        vec![5, inf, 0, 1],
        vec![2, inf, inf, 0],
    ];
    println!("{}", floyd_warshall(&mat)[0][2]);
}