[Algo] 플로이드 c++

* 언제 사용?

• 모든 정점간의 최단거리를 구할때 사용
• 시간복잡도 : O(n^3), n=100일때가 정해. n=1000일때도 비빌수는 있음.
• 인접리스트보다는 행렬이 유리!

• 다익스트라 : 한시작점에서 다른 모든 정점의로의 최단거리 구하는 알고리즘 / O(V ElgE)

 

* 의사코드

• 3중 for문을 돌면서
• 정점 k를 하나씩 추가해가면서 이걸 거쳐서 가는게 싼지 탐색
• k의 for문은 맨 밖에 둬야함에 주의.
• 연산이 대입보다 빠르기때문에, min보다는 if(d[i][j] > d[i][k]+d[k][j]) 인경우 대입하도록 바꾸면 n=1000도 비빌수있음.

 

* 전체코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int INF = 0x3f3f3f3f;
int d[105][105]; //i에서 j로 가는 거리
int n, m;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    fill(&d[0][0], &d[0][0] + 105 * 105, INF); //무한대로 초기화

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }

    for (int i = 1; i <= n; ++i) d[i][i] = 0; //자기자신으로 가는비용은 0

    for (int k = 1; k <= n; ++k) { //정점 k를 하나씩 추가하면서
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                //d[2][3] = d[2][3] , d[2][1]+d[1][2] 
                //(정점 k를 거쳐가는게 더싼지 계산) 
                //연산이 대입보다 빠르기때문에, 이렇게 연산조건문으로 바꾸면
                // N이 1000일때도 비빌수있음!
                if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
                //d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (d[i][j] == INF) cout << 0 << " ";
            else cout << d[i][j] << " ";
        }
        cout << "\n";
    }
    


    return 0;
}

 

* 레퍼런스

https://www.youtube.com/watch?v=dDDy2bEZRA8