플로이드 와샬 (Floyd-Warshall)

그래프에서 최단 경로를 구하는 방법은 여러가지가 있다. 모든 정점에서 모든 정점까지의 최단 경로(비용)를 구할 때는 플로이드 와샬 알고리즘을 사용한다.

그래프는 이중 vector 형태로 저장하고, 삼중 for문을 돌면서 비용을 갱신한다.

아이디어의 핵심 코드는 다음과 같다.
i를 거쳐서 지나가는 경우 즉 j -> i -> k로 가는 비용이 더 작다면 vec[j][k]를 갱신한다.

for (int i = 1; i <= n; i++) { // 거쳐가는 점
    for (int j = 1; j <= n; j++) { // 출발점
        for (int k = 1; k <= n; k++) { // 도착점
            if (vec[j][k] > vec[j][i] + vec[k][i]) {
                vec[j][k] = vec[j][i] + vec[k][i];
            }
        }
    }
}