[C++] DP - 플로이드 워샬 알고리즘(최단거리 , 모든 N과 모든 N의 관계)

모든 도시에서 모든 도시로 가는 최소비용

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    
    int n,m,a,b,c;
    cin >> n >> m;
    vector<vector<int>> dis(n+1,vector<int>(n+1,5000));
    for(int i = 1; i <= n; i++)dis[i][i] = 0; //자기 자신으로 가는건 0
    for(int i = 1; i <= m; i++){
        cin >> a>> b>> c;
        dis[a][b] = c;
    }
    
    for(int k = 1; k <= n; k++) {//1~n가지의 경유지 k를 모두 들린다.
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(dis[i][j] == 5000) cout <<"M ";
            else cout << dis[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

• 다익스트라나 벨만포드는 한 정점에서 다른 정점으로 가는 최단거리였다면
• 플로이드 워샬 알고리즘은 그래프에서 모든 정점으로부터 모든 정점까지의 최소비용을 구한다.
• 따라서, 플로이드 워샬의 Dynamic Table은 2차원이며
• 냅색 알고리즘과 동일한 원리의 점화식으로 구현한다.

풀이

1. 다이나믹 테이블을 만들고, 큰 수로 초기화한다.(최소 비용이 들어갈 것이기 때문에)

• 인덱스 의미 : 행번호 노드에서 열번호 노드로 이동
• 값 의미 : 최소비용
• 즉, row index에서 col index로 가는 최소 비용

2. 다이나믹 테이블에 입력 값을 할당한다. (자기 자신으로 가는 것은 0이다)

• 입력값을 dy table에 할당했다는 것은 경유지가 없이 곧바로 이동할 수 있다는 것이다.
• 하지만, 곧바로 이동한다고 해서 최소 비용은 아님 나중에 relax될 수 있음.

3. 이제 경유지(k)를 정해놓고, 출발노드(i)에서 도착노드(j)까지 갈 때, k를 거치는 것이 더 최소비용인지를 판단한다.

• 냅색에서 동전의 종류, 보석의 종류에 따라 dy table이 relax됐는데 플로이드 워샬은 경유지의 종류에 따라 relax될 것이다.

for(int k = 1; k <= n; k++) {//1~n가지의 경유지 k를 모두 들린다.
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
                //i -> k -> j
            }
        }
    }

• 1번 경유지를 거칠 때에는 변화가 없다.(모든 노드는 1번으로 이동할 수 없기 때문에, 큰 수 5000으로 할당돼있음)

1번 경유지를 거치면 dis[i,1]+dis[1,k]인데, dis[i,1]이 전부 5000이라서 변화가 없다.

• 2번 경유지를 거칠 때에는 dis[1,4] dis[1,5] dis[3,4] dis[3,5]에서 값이 relax되었다.

dis[1,4] dis[1,5] dis[3,4] dis[3,5]는 2번 경유지를 거쳐야 더 최소비용임을 알 수 있다.

• 3번 경유지를 거칠 때에는 dis[1,2] dis[1,4] dis[1,5]의 값이 relax된다. 즉 dis[1,2] : 5라는 값은 1 -> 3 -> 5경로의 값이다.
• 여기서 주의 1 : dis[1,4] dis[1,5]는 이미 2번 경유지를 거쳤을 때 relax된 최소비용이다. 그래서 현재 dis[1,4] :6라는 값과 dis[1,5] : 18이라는 값은 2번과 3번 경유지를 모두 거쳐서 relax된 최소비용이라는 것이다.
• 여기서 주의 2 : 그럼 현재 dis[1,4]는 1 -> 2 -> 3 -> 4 경로의 값이냐?라고 생각할 수 있는데 아니다. 경유지를 거치는 2 - > 3이라는 순서는 순열이다. 3 -> 2가 될 수도 있다. 알아서 최적의 경로 값이 담기게 된다.
• 실제로 현재 dis[1,4]와 dis[1,5]는 모두 1 -> 3 -> 2 -> 4/5 를 거친다.

• 이런식으로 5번 경유지까지 거치면 완성된 dynamic table이 완성된다. 여기서 5000으로 relax되지 않은 값은 갈 수 없는 것을 의미하게 된다.

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard