---
title: "음수가 있거나 모든 쌍이 필요할 때"
description: "비용이 가장 적은 후보부터 확정하는 방식이 안 통하는 두 경우입니다. 음수 간선을 다루는 벨만-포드(Bellman-Ford)와 모든 쌍의 거리를 한 번에 구하는 플로이드-워셜(Floyd-Warshall), 그리고 셋 중 무엇을 고를지."
author: "유니얼"
pubDate: 2026-09-17
updatedDate: 2026-09-18
category: "programming/algorithm/graph"
tags: ["탐색"]
canonical: https://blog.unialgames.com/posts/algo-bellman-ford-floyd/
---
비용이 가장 적은 후보부터 꺼내 확정하는 방식은 두 가지를 전제합니다.
**모든 간선 비용이 0 이상**이고, 알고 싶은 것이 **한 지점에서 출발하는 거리**라는 것입니다.
둘 중 하나가 깨지는 경우가 있습니다.
- 어떤 이동은 비용이 음수다. 지나가면 오히려 자원이 늘어난다
- 출발지가 정해져 있지 않다. **모든 지역에서 모든 지역까지의 거리표**가 필요하다
각각에 맞는 알고리즘이 따로 있습니다.
## 음수가 있으면 확정을 미룬다
**벨만-포드 알고리즘(Bellman-Ford algorithm)** 은 확정이라는 개념을 아예 쓰지 않습니다.
대신 **모든 간선을 훑으면서 더 싼 길이 발견되면 값을 고치는 일**을 여러 번 반복합니다.
간선 하나를 보고 `dist[to]` 를 더 작게 고치는 것을 완화(relaxation)라고 부릅니다.
```csharp
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을 밀어냅니다.
**한 라운드가 간선 하나만큼만 정보를 옮긴다**는 것이 여기서 보입니다. 그래서 반복 횟수가 정점 수에 걸려 있습니다.
마지막에 한 번 더 도는 라운드는 값을 고치지 않고 확인만 합니다. 거기서도 줄어든다면 그건 다른 문제입니다.
**라운드 한 번마다 정보가 간선 하나만큼 더 퍼집니다.**
| 라운드 | 확실해지는 것 |
| --- | --- |
| 1 | 간선 하나로 닿는 정점까지의 최단 |
| 2 | 간선 두 개로 닿는 정점까지의 최단 |
| k | 간선 k 개로 닿는 정점까지의 최단 |
최단 경로는 같은 정점을 두 번 지나지 않으니 간선이 **정점 수보다 하나 적게** 쓰입니다.
그래서 `V - 1` 라운드면 충분합니다. 중간에 아무것도 안 바뀌면 그 자리에서 멈춰도 됩니다.
## 한 번 더 돌려서 음수 순환을 잡는다
`V - 1` 라운드를 마쳤는데 **한 번 더 돌렸을 때 또 줄어든다면** 그건 무한히 줄어들 수 있다는 뜻입니다.
돌면 돌수록 비용이 내려가는 순환, 즉 음수 순환이 있는 것입니다.
```csharp
foreach (var (from, to, w) in edges) {
if (dist[from] + w < dist[to]) {
// 음수 순환이 있다. 최단 경로가 정의되지 않는다
}
}
```
게임에서 이 검사가 쓰이는 자리는 길찾기보다 **데이터 검증**입니다.
교환이나 제작 비용표를 데이터로 만들다 보면, 몇 단계를 돌고 오면 재료가 늘어나는 조합이 생깁니다.
그런 순환을 사람이 표에서 찾기는 어렵지만, 그래프로 만들어 한 번 돌리면 나옵니다.
비용은 **`O(V × E)`** 입니다. 간선 전부를 정점 수만큼 훑기 때문입니다.
같은 그래프에서 다익스트라가 `O(E log V)` 이니 훨씬 느립니다.
**음수 간선이 없으면 쓸 이유가 없습니다.**
## 모든 쌍이 필요하면 경유지를 하나씩 늘린다
지역이 서른 개 있고, 어디서 어디로든 이동 비용을 알아야 합니다.
출발지마다 다익스트라를 서른 번 돌려도 되지만, **플로이드-워셜 알고리즘(Floyd-Warshall algorithm)** 은 다른 방식으로 접근합니다.
발상이 한 줄입니다. **"경유지로 쓸 수 있는 정점을 하나씩 늘려 간다."**
```csharp
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` 가 바깥에 있는 것이 이 코드의 전부입니다.
`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²)` 입니다. 정점 수가 조금만 커져도 감당이 안 됩니다.
| 정점 수 | 연산 횟수 | 표 크기 (float) |
| --- | --- | --- |
| 30 | 2만 7천 | 3.6KB |
| 100 | 100만 | 40KB |
| 500 | 1억 2천만 | 1MB |
| 10,000 (격자 100×100) | 1조 | 400MB |
**격자 맵에는 절대 쓰지 않습니다.** 칸 하나가 정점이면 정점이 수만 개라 시작도 못 합니다.
반대로 **지역이나 방처럼 정점이 수십 개인 그래프에는 잘 맞습니다.**
로딩할 때 한 번 돌려 표를 만들어 두면, 런타임에는 "여기서 저기까지 얼마" 를 배열 조회 한 번으로 답합니다.
워프 비용표, 퀘스트 목적지 정렬, AI 가 여러 후보 중 가장 가까운 거점을 고르는 판단이 전부 조회로 끝납니다.
## 셋 중 무엇을 고르나
| 상황 | 무엇을 쓰나 | 비용 |
| --- | --- | --- |
| 출발지 하나, 비용이 전부 0 이상 | 다익스트라 | `O(E log V)` |
| 출발지 하나, 목표도 하나 | A 스타 | 다익스트라보다 좁게 |
| 출발지 하나, 음수 간선이 있다 | 벨만-포드 | `O(V × E)` |
| 모든 쌍이 필요하고 정점이 적다 | 플로이드-워셜 | `O(V³)` |
| 모든 쌍이 필요하고 정점이 많고 간선이 적다 | 출발지마다 다익스트라 | `O(V × E log V)` |
마지막 줄이 실무에서 자주 맞습니다. 정점이 1,000개인데 간선이 3,000개뿐이면
플로이드-워셜의 10억 번보다 다익스트라를 1,000번 도는 쪽이 훨씬 적게 듭니다.
**표가 촘촘하냐 성기냐가 가르는 기준입니다.**
## 게임에서 음수 비용이 진짜 필요한가
대개는 아닙니다. 음수로 만들고 싶어지는 것들은 보통 다른 방법으로 표현됩니다.
| 하고 싶은 것 | 음수 대신 |
| --- | --- |
| 지나가면 마나가 차는 지형 | 비용을 아주 작은 양수로. 마나는 이동 비용과 다른 축으로 관리 |
| 순간이동이 일반 이동보다 싸다 | 그냥 싼 양수 간선. 0도 괜찮습니다 |
| 버프를 받으면 이동이 빨라진다 | 상태마다 그래프를 나누거나, 비용을 상태에 따라 다시 계산 |
**모든 비용에 같은 값을 더해 양수로 옮기는 방법은 조심해야 합니다.**
간선 수가 다른 두 경로에 더해지는 양이 달라져서, 짧은 경로가 부당하게 유리해집니다.
답이 바뀌어도 되는 상황인지 먼저 확인해야 합니다.
## 정리
비용이 가장 적은 후보부터 확정하는 방식이 안 되는 두 경우에 각각 다른 도구가 있습니다.
- **벨만-포드**는 확정 없이 모든 간선을 `V - 1` 번 훑으며 값을 고칩니다. 라운드 하나가 간선 하나만큼의 정보를 퍼뜨립니다. 한 번 더 돌려서 줄어들면 음수 순환입니다
- **플로이드-워셜**은 경유지를 하나씩 늘리는 3중 루프입니다. `k` 가 바깥에 있어야 하고, 정점 수의 세제곱이라 **정점이 수십 개일 때만** 씁니다
- 대부분의 게임 상황은 여전히 다익스트라와 A 스타입니다. 음수가 필요해 보이면 **비용 설계를 먼저 의심하세요**