음수가 있거나 모든 쌍이 필요할 때

비용이 가장 적은 후보부터 꺼내 확정하는 방식은 두 가지를 전제합니다. 모든 간선 비용이 0 이상이고, 알고 싶은 것이 한 지점에서 출발하는 거리라는 것입니다.

둘 중 하나가 깨지는 경우가 있습니다.

• 어떤 이동은 비용이 음수다. 지나가면 오히려 자원이 늘어난다
• 출발지가 정해져 있지 않다. 모든 지역에서 모든 지역까지의 거리표가 필요하다

각각에 맞는 알고리즘이 따로 있습니다.

음수가 있으면 확정을 미룬다

벨만-포드 알고리즘(Bellman-Ford algorithm) 은 확정이라는 개념을 아예 쓰지 않습니다. 대신 모든 간선을 훑으면서 더 싼 길이 발견되면 값을 고치는 일을 여러 번 반복합니다. 간선 하나를 보고 dist[to] 를 더 작게 고치는 것을 완화(relaxation)라고 부릅니다.

var dist = new float[v];
Array.Fill(dist, float.PositiveInfinity);
dist[start] = 0f;

for (int round = 0; round < v - 1; round++) {
    bool changed = false;

    foreach (var (from, to, w) in edges) {
        if (float.IsInfinity(dist[from])) continue;
        if (dist[from] + w >= dist[to]) continue;
        dist[to] = dist[from] + w;
        changed = true;
    }

    if (!changed) break;        // 더 고칠 게 없으면 끝
}

한 라운드에 무슨 일이 일어나는지 보면 반복 횟수가 이해됩니다.

B → A 간선의 비용이 -1 입니다. 음수라 확정 방식으로는 다룰 수 없는 그래프입니다.

첫 라운드에서는 A → G 와 B → A 를 훑지만 A 와 B 가 아직 무한대라 아무것도 못 합니다. 그다음 S → B 와 S → A 를 보면서 2와 4가 정해집니다. 이번 라운드에 정해진 것은 S 에서 한 칸 거리뿐입니다.

두 번째 라운드에서 B → A 가 값을 합니다. B 가 2이니 A 는 2 - 1 = 1, 먼저 적어 둔 4보다 쌉니다. 이미 정해 둔 값을 고치는 것이 이 알고리즘의 전부입니다. 확정이 없으니 언제든 고칠 수 있습니다.

세 번째 라운드에서 그 고침이 G 까지 전해집니다. A → G 가 1 + 3 = 4 로 앞서 적은 7을 밀어냅니다. 한 라운드가 간선 하나만큼만 정보를 옮긴다는 것이 여기서 보입니다. 그래서 반복 횟수가 정점 수에 걸려 있습니다.

마지막에 한 번 더 도는 라운드는 값을 고치지 않고 확인만 합니다. 거기서도 줄어든다면 그건 다른 문제입니다.

라운드 한 번마다 정보가 간선 하나만큼 더 퍼집니다.

최단 경로는 같은 정점을 두 번 지나지 않으니 간선이 정점 수보다 하나 적게 쓰입니다. 그래서 V - 1 라운드면 충분합니다. 중간에 아무것도 안 바뀌면 그 자리에서 멈춰도 됩니다.

한 번 더 돌려서 음수 순환을 잡는다

V - 1 라운드를 마쳤는데 한 번 더 돌렸을 때 또 줄어든다면 그건 무한히 줄어들 수 있다는 뜻입니다. 돌면 돌수록 비용이 내려가는 순환, 즉 음수 순환이 있는 것입니다.

foreach (var (from, to, w) in edges) {
    if (dist[from] + w < dist[to]) {
        // 음수 순환이 있다. 최단 경로가 정의되지 않는다
    }
}

게임에서 이 검사가 쓰이는 자리는 길찾기보다 데이터 검증입니다. 교환이나 제작 비용표를 데이터로 만들다 보면, 몇 단계를 돌고 오면 재료가 늘어나는 조합이 생깁니다. 그런 순환을 사람이 표에서 찾기는 어렵지만, 그래프로 만들어 한 번 돌리면 나옵니다.

비용은 O(V × E) 입니다. 간선 전부를 정점 수만큼 훑기 때문입니다. 같은 그래프에서 다익스트라가 O(E log V) 이니 훨씬 느립니다. 음수 간선이 없으면 쓸 이유가 없습니다.

모든 쌍이 필요하면 경유지를 하나씩 늘린다

지역이 서른 개 있고, 어디서 어디로든 이동 비용을 알아야 합니다. 출발지마다 다익스트라를 서른 번 돌려도 되지만, 플로이드-워셜 알고리즘(Floyd-Warshall algorithm) 은 다른 방식으로 접근합니다.

발상이 한 줄입니다. “경유지로 쓸 수 있는 정점을 하나씩 늘려 간다.”

for (int k = 0; k < v; k++)          // k 를 경유지로 허용
    for (int i = 0; i < v; i++)
        for (int j = 0; j < v; j++)
            if (dist[i, k] + dist[k, j] < dist[i, j])
                dist[i, j] = dist[i, k] + dist[k, j];

k 가 바깥에 있는 것이 이 코드의 전부입니다. k 번째 루프가 시작될 때 dist[i, j] 는 0번부터 k-1번까지만 경유지로 써서 얻은 최단입니다. 거기에 k 를 허용하면 “i 에서 k 로 갔다가 k 에서 j 로 가는” 길만 새로 생기므로, 두 값을 더해 비교하면 됩니다.

세 루프의 순서를 바꾸면 틀립니다. k 를 안쪽으로 옮기면 “아직 허용 안 된 경유지” 를 쓴 값이 섞여 들어갑니다. 외우기보다 k 가 바깥이어야 하는 이유를 기억하는 편이 낫습니다.

초기값은 이렇게 둡니다.

• dist[i, i] = 0
• 간선이 있으면 dist[i, j] = 비용
• 없으면 무한대. float.PositiveInfinity 를 쓰면 더하기에서 넘칠 걱정이 없습니다

경로까지 복원하려면 표를 하나 더 둡니다. next[i, j] 에 “i 에서 j 로 갈 때 첫 걸음” 을 적어 두고, 값을 고칠 때마다 next[i, j] = next[i, k] 로 같이 고칩니다.

비용이 정점 수의 세제곱이다

3중 루프이니 O(V³) 이고 메모리는 O(V²) 입니다. 정점 수가 조금만 커져도 감당이 안 됩니다.

격자 맵에는 절대 쓰지 않습니다. 칸 하나가 정점이면 정점이 수만 개라 시작도 못 합니다.

반대로 지역이나 방처럼 정점이 수십 개인 그래프에는 잘 맞습니다. 로딩할 때 한 번 돌려 표를 만들어 두면, 런타임에는 “여기서 저기까지 얼마” 를 배열 조회 한 번으로 답합니다. 워프 비용표, 퀘스트 목적지 정렬, AI 가 여러 후보 중 가장 가까운 거점을 고르는 판단이 전부 조회로 끝납니다.

셋 중 무엇을 고르나

마지막 줄이 실무에서 자주 맞습니다. 정점이 1,000개인데 간선이 3,000개뿐이면 플로이드-워셜의 10억 번보다 다익스트라를 1,000번 도는 쪽이 훨씬 적게 듭니다. 표가 촘촘하냐 성기냐가 가르는 기준입니다.

게임에서 음수 비용이 진짜 필요한가

대개는 아닙니다. 음수로 만들고 싶어지는 것들은 보통 다른 방법으로 표현됩니다.

모든 비용에 같은 값을 더해 양수로 옮기는 방법은 조심해야 합니다. 간선 수가 다른 두 경로에 더해지는 양이 달라져서, 짧은 경로가 부당하게 유리해집니다. 답이 바뀌어도 되는 상황인지 먼저 확인해야 합니다.

정리

비용이 가장 적은 후보부터 확정하는 방식이 안 되는 두 경우에 각각 다른 도구가 있습니다.

• 벨만-포드는 확정 없이 모든 간선을 V - 1 번 훑으며 값을 고칩니다. 라운드 하나가 간선 하나만큼의 정보를 퍼뜨립니다. 한 번 더 돌려서 줄어들면 음수 순환입니다
• 플로이드-워셜은 경유지를 하나씩 늘리는 3중 루프입니다. k 가 바깥에 있어야 하고, 정점 수의 세제곱이라 정점이 수십 개일 때만 씁니다
• 대부분의 게임 상황은 여전히 다익스트라와 A 스타입니다. 음수가 필요해 보이면 비용 설계를 먼저 의심하세요