# Floyd-Warshall

Floyd-Warshall은 모든 정점 쌍 사이의 최단거리를 구하는 `O(N^3)` 동적 계획법입니다. Dijkstra나 Bellman-Ford가 한 시작점에서의 최단거리를 구한다면, Floyd-Warshall은 정점 수가 작고 모든 쌍의 관계가 필요할 때 쓰기 좋습니다.

## 언제 쓰는가

Floyd-Warshall은 정점 수가 작을 때 모든 쌍 정보를 단순하게 얻는 도구입니다.

| 문제 신호 | Floyd-Warshall 관점 |
| --- | --- |
| 모든 도시 쌍 최단거리가 필요하다 | APSP |
| 정점 수가 300 이하 정도다 | `O(N^3)` 가능성 검토 |
| 경유지를 여러 개 써도 된다 | 중간 정점 DP |
| 도달 가능성만 묻는다 | boolean transitive closure |
| 음수 간선이 있지만 음수 사이클은 없다 | 최단거리 가능 |

`N`이 수만이면 Floyd-Warshall은 맞지 않습니다. 그때는 시작점마다 Dijkstra를 돌리거나, 그래프 구조를 더 활용해야 합니다.

## DP 의미

![0에서2로 직접10, 1을 거치면3+4=7입니다. k=1 단계에서 중간 정점1을 허용하며 갱신합니다.](lesson-assets/structure-trace.svg)

[그림 크게 보기](https://git.readiz.com/h-contest-lesson/lessons/floyd-warshall/lesson-assets/structure-trace.svg)

간선이 `0→1:3`, `1→2:4`, `0→2:10`인 예시입니다. 각 단계는 지금까지 허용한 정점 집합 안에서 경유지를 선택한 최단거리입니다.

반복문의 `k`는 "0..k번 정점만 중간 정점으로 사용할 수 있다"는 뜻입니다.

```text
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
```

`i -> j`로 바로 가는 기존 최단거리와, `i -> k -> j`로 나눠 가는 경로를 비교합니다. `k`를 바깥 반복문에 두어야 이 DP 의미가 유지됩니다.

## 기본 구현

아래 구현은 0-index 정점과 `long long` 거리를 사용합니다. 도달 불가는 코드와 같은 `INF = LLONG_MAX / 4`로 초기화합니다. 간선 비용의 절댓값 상한이 `W`라면 `N * W < INF`인 범위에서 사용합니다. 이 조건은 음수 사이클의 영향을 받지 않는 유한 최단거리를 `(-INF, INF)` 안에 둡니다.

음수 사이클이 있으면 중간 값은 단순 경로 길이보다 훨씬 작아질 수 있습니다. 서로 다른 모든 정점 사이의 비용이 `-1`인 30정점 그래프도 원래 덧셈만 반복하면 `long long`을 넘칩니다. 그래서 각 갱신에서 하한을 `-INF`로 제한합니다. 두 피연산자가 `[-INF, INF)` 안에 있으므로 **하한을 적용하기 전 덧셈도** 정수 범위 안입니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <algorithm>
#include <limits>
#include <vector>
using namespace std;

vector<vector<long long>> floydWarshall(vector<vector<long long>> dist) {
    const long long INF = numeric_limits<long long>::max() / 4;
    int n = (int)dist.size();

    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            if (dist[i][k] == INF) {
                continue;
            }
            for (int j = 0; j < n; ++j) {
                if (dist[k][j] == INF) {
                    continue;
                }
                long long through = max(-INF, dist[i][k] + dist[k][j]);
                dist[i][j] = min(dist[i][j], through);
            }
        }
    }

    return dist;
}

vector<vector<bool>> negativeCyclePairs(const vector<vector<long long>>& dist) {
    const long long INF = numeric_limits<long long>::max() / 4;
    int n = (int)dist.size();
    vector<vector<bool>> affected(n, vector<bool>(n, false));
    for (int v = 0; v < n; ++v) {
        if (dist[v][v] >= 0) continue;
        for (int i = 0; i < n; ++i) {
            if (dist[i][v] == INF) continue;
            for (int j = 0; j < n; ++j) {
                if (dist[v][j] != INF) affected[i][j] = true;
            }
        }
    }
    return affected;
}
```

초기화는 `dist[i][i] = 0`, 간선 `u -> v`에 대해 `dist[u][v] = min(dist[u][v], w)`입니다. 무방향 그래프면 반대 방향도 같이 넣습니다. 다중 간선은 가장 작은 비용만 남기고, 경로가 없는 `INF` 값은 덧셈에서 제외합니다.

## 경로 복원

최단거리뿐 아니라 실제 경로가 필요하면 `next[i][j]`를 저장합니다. `next[i][j]`는 `i`에서 `j`로 가는 최단 경로의 첫 다음 정점입니다.

```cpp compile-check
#include <algorithm>
#include <limits>
#include <vector>
using namespace std;

vector<int> restorePath(int start, int target, const vector<vector<int>>& nextVertex) {
    if (nextVertex[start][target] == -1) {
        return {};
    }

    vector<int> path{start};
    while (start != target) {
        start = nextVertex[start][target];
        path.push_back(start);
    }
    return path;
}

void relaxPath(
    int i,
    int j,
    int k,
    vector<vector<long long>>& dist,
    vector<vector<int>>& nextVertex
) {
    const long long INF = numeric_limits<long long>::max() / 4;
    if (dist[i][k] == INF || dist[k][j] == INF) return;
    long long through = max(-INF, dist[i][k] + dist[k][j]);
    if (through < dist[i][j]) {
        dist[i][j] = through;
        nextVertex[i][j] = nextVertex[i][k];
    }
}
```

`next[i][i] = i`로 두면 자기 자신으로 가는 길도 `[i]`로 복원합니다. 초기에는 간선이 있는 `i -> j`에 대해 `next[i][j] = j`로 둡니다. 경로가 없으면 `-1`입니다. `relaxPath`는 기본 구현과 같은 `k, i, j` 순서에서 거리 갱신을 대신하며, 내부에서 두 `INF` 검사와 하한 처리를 수행합니다. 계산 후 `negativeCyclePairs(dist)[start][target]`이 true인 쌍에는 최단 경로가 없으므로 복원하지 않습니다. 여러 질의를 처리한다면 이 영향 행렬도 한 번만 계산합니다.

## 도달 가능성만 필요할 때

거리 대신 도달 여부를 저장해도 같은 순서로 계산합니다. `reachable[i][j]`를 갱신할 식은 `reachable[i][j] || (reachable[i][k] && reachable[k][j])`입니다. 기존 경로가 있거나, `k`까지 갈 수 있고 `k`에서 목적지로 갈 수 있으면 연결된 것입니다.

## 음수 사이클

Floyd-Warshall이 끝난 뒤 `dist[v][v] < 0`인 정점이 있으면 음수 사이클이 있습니다. 그 정점을 거쳐 갈 수 있는 `i, j` 쌍은 최단거리가 정의되지 않습니다.

```text
if dist[i][v] != INF and dist[v][v] < 0 and dist[v][j] != INF:
    i -> j 최단거리는 -infinity 영향을 받음
```

위 구현의 `negativeCyclePairs`가 이 조건을 모든 쌍에 적용합니다. 결과는 다음 세 가지로 읽습니다.

| 조건 | 의미 |
| --- | --- |
| `dist[i][j] == INF` | 도달 불가 |
| `affected[i][j] == true` | 음수 사이클을 반복할 수 있어 유한한 최솟값이 없음 |
| 나머지 | `dist[i][j]`가 유한 최단거리 |

`-INF`는 계산 중 오버플로를 막기 위한 하한일 뿐, 영향 여부를 판정하는 기준이 아닙니다. 음수 사이클의 영향을 받아도 값이 하한까지 내려가지 않을 수 있습니다.

예를 들어 `0→1:3`, `1→2:-2`, `2→1:1`, `2→3:4`, `0→4:9`이면 `1→2→1`의 비용이 `-1`입니다. `0→3`은 이 사이클을 반복한 뒤 도착할 수 있어 최솟값이 없지만, `0→4`의 최단거리는 여전히 `9`이고 `4→0`은 도달 불가입니다. 그래프에 음수 사이클이 있다는 이유로 모든 쌍을 같은 상태로 표시하면 안 됩니다.

## 시간 복잡도

| 작업 | 시간 | 메모리 |
| --- | ---: | ---: |
| 거리 초기화 | `O(N^2 + M)` | `O(N^2)` |
| Floyd-Warshall | `O(N^3)` | `O(N^2)` |
| 음수 사이클 영향 쌍 표시 | `O(N^3)` | `O(N^2)` |
| transitive closure | `O(N^3)` | `O(N^2)` |
| 경로 복원 1회 | 경로 길이 | `next` matrix |

`N = 500`이면 `125,000,000`번 갱신이라 언어와 제한에 따라 빡빡할 수 있습니다. `N = 1000`이면 보통 일반 Floyd-Warshall은 어렵습니다.

## 로컬 연습: 여러 출발점의 거리 질의

비음수 방향 그래프의 Q개 출발점·도착점 쌍에 대해 최소 비용을 구하세요.

**입력:** N M Q, M줄의 u v w, Q줄의 s t. 1 <= N <= 300, 0 <= M <= 90000, 0 <= Q <= 100000, 0 <= w <= 10^9, 정점은 0-based입니다.

**출력:** 질의마다 최소 비용을 출력하고 도달 불가이면 UNREACHABLE을 출력합니다.

### 예시

```text exercise=floyd-warshall role=input
4 4 4
0 1 5
1 2 2
0 2 10
2 0 1
0 2
2 1
3 0
3 3
```

```text exercise=floyd-warshall role=output
7
6
UNREACHABLE
0
```

**확인 방법:** 대각 원소는 0, 평행 간선은 최소 비용으로 초기화합니다. 거쳐 갈 수 없는 INF 항을 더하지 않습니다. 모든 시작점에서 Dijkstra를 실행한 결과와 비교하고, k 반복문을 바깥에 두는 이유를 허용 경유지 집합으로 설명합니다.