[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘

문제 정의

• 여러개의 노드에서 다른 노드까지의 최소 비용을 구할때
  • 한 노드에서 다른 노드까지 최소비용을 구하는 문제라면 다익스트라를 사용하는 것이 이득
  • Floyd를 사용할경우 O(V^3)
  • 다익스트라 : O(ElgE)
• 노드 끼리의 순위가 일부 주어졌을떄, 전체 중 노드의 순위를 구하는 문제

문제 접근

• 노드 A에서 B까지 가는데 다른 노드(C)를 거쳐서 갈경우 더 비용이 적으면 갱신
• A,B,C를 모두 V번 반복

시간복잡도

• 노드를 3번 순회해야함 >> O(V^3)

대표예제 : 백준 11404 플로이드

#include <iostream>
#include <vector>
 
using namespace std;
 
const int inf = 1e8+10;
int map[110][110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&map[0][0], &map[109][110], inf);
    
    int V,E; cin >> V >> E;
    
    // 자기 자신으로 가는 비용은 0으로 초기화
    for(int i=1; i<=V; i++) map[i][i] = 0;
    
    for(int i=0; i<E; i++) {
        int a,b,c; cin >> a >> b >> c;
        map[a][b] = min(c, map[a][b]);
    }
    
    
    for(int k=1; k<=V; k++) {
        for(int j=1; j<=V; j++) {
            for(int i=1; i<=V; i++) {
                // k를 거치는 경우 더 비용이 작으면 갱신
                // 이때 다음 노드는 k가 아닌, j에서 k로 가는 노드로 대체
                if(map[j][i] > map[j][k] + map[k][i]) {
                    map[j][i] = map[j][k] + map[k][i];
                }
            }
        }
    }
    
    for(int j=1; j<=V; j++) {
        for(int i=1; i<=V; i++) {
            if(map[j][i] == inf) cout << 0 << ' ';
            else cout << map[j][i] << ' ';
        }
        cout << '\n';
    }
        
    
    return 0;
    
}

문제 유형

• 플로이드 경로 구하기 : https://www.acmicpc.net/problem/11780
• 순위 구하기 : https://www.acmicpc.net/problem/2458