플로이드 와샬 알고리즘

https://m.blog.naver.com/PostView.naver?blogId=kks227&logNo=220797649276&referrerCode=0&searchKeyword=%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C 

플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)

 

아직 전부 이해는 못했지만..

- 모든 정점 쌍 사이의 최단 경로를 한번에 구할 수 있다

- 시간복잡도 O(V^3)

 

- i, j, k

- i번 정점에서 j번 정점까지, 1~k번 정점만 사용할 떄의 최단 거리를 구하라

- dist에는 1 ~ k-1번 정점만 사용해서 나올 수 있는 최단 거리가 이미 남아있다

- if (dist[i][j] > dist[i][k] + dist[k][j])

- i, j에 대해 k번 정점을 사용해 우회하면 지금보다 최단 거리가 짧아지는가?

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include<cassert>
#include <climits>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 987654321

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int dist[100][100];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = i == j ? 0 : MAXV;
    
    for (int i = 0; i < m; i++) {
        int u, v;
        int d;
        scanf("%d %d %d", &u, &v, &d);
        dist[u-1][v-1] = min(dist[u-1][v-1], d);
    }
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == MAXV) 
                printf("0 ");
            else 
                printf("%d ", dist[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}