[백준 11404] 플로이드 C++

11404번: 플로이드

최단경로  플로이드-와샬 알고리즘

 

11404문제 예제 입력의 그래프이다

숫자가 겹쳐보이는 이유는 1 4 1 , 1 4 2 처럼 1번에서 4번 노드로 가는 경우의 비용이 중복되어서 입력되기 때문이다

 

플로이드-와샬 알고리즘은 동적계획법을 활용한 알고리즘이다

그래서 임의의 vertax 에서 다른 vertax로 가는 모든 경우의 수를 조사해서 최소 비용을 구할 수 있다.

그리고 다익스트라 최단거리 알고리즘은 edge의 비용이 음수인 경우는 찾지 못하는 반면

플로이드-와샬 알고리즘은 비용이 음수인지에 상관없이 최소 비용을 구할 수 있다.

 

특정 vertax를 경유하는 모든 경우의 수를 한 번씩 탐색하기 때문에

공간복잡도 : O(n^3)  시간복잡도 : O(n^3)

 

 

문제에 사용된 dp배열의 해석

• dp[0][r][c] = r번에서 c번으로 이동하는 최소 비용
• dp[1][r][c] = 1번을 경유해서 r번에서 c번으로 이동하는 최소 비용
• dp[2][r][c] = 1, 2번을 경유해서 r번에서 c번으로 이동하는 최소 비용
• dp[3][r][c] = 1, 2, 3번을 경유해서 r번에서 c번으로 이동하는 최소 비용
• dp[4][r][c] = 1, 2, 3, 4번을 경유해서 r번에서 c번으로 이동하는 최소 비용
• dp[5][r][c] = 1, 2, 3, 4, 5번을 경유해서 r번에서 c번으로 이동하는 최소 비용

결국 r에서 c로 가는 최소비용은 i를 거치지 않고 c로 가는 경우 또는 i를 거쳐서 c로 가는 경우 중 최솟값이 된다

점화식 : dp[i][r][c] = min(dp[i-1][r][c], dp[i-1][r][i] + dp[i-1][i][c]);

 

#include <iostream>
 
using namespace std;
 
const int INF = 1e9+7;
 
int dp[101][101][101];
int N, M;
 
void process(){
    for(int i = 1; i <= N; i++){
        // i까지 경유 가능
        
        //r에서 c까지 갈 때 i이하를 경유가능할 때 최단거리
        for(int r = 1; r <= N; r++){
            
            for(int c = 1; c <= N; c++){
                if(r == c){
                    dp[i][r][c] = 0;
                    continue;
                }
                dp[i][r][c] = min(dp[i-1][r][c], dp[i-1][r][i] + dp[i-1][i][c]);
            }
        }
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if(dp[N][i][j] >= 1e9+7) cout << 0 << " ";
            else cout << dp[N][i][j] << " ";
        }
        cout << "\n";
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M;
    
    int s, d, c;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            dp[0][i][j] = INF;
        }
    }
    
    for(int i = 1; i <= M; i++){
        cin >> s >> d >> c;
        dp[0][s][d] = min(dp[0][s][d], c);
    }
    
    process();
    
    return 0;
}