BOJ 11404 - 플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

플로이드 와샬 알고리즘은

그래프 상에서 모든 정점 쌍 사이에 최단거리를 갱신하는 알고리즘으로,

O(V^3) 의 시간 복잡도를 갖는 알고리즘이다 (V 는 노드의 갯수)

 

플로이드 와샬 알고리즘의 핵심은 

정점 A 에서 B 로 가는 최단거리를 구하되, 중간에 거쳐가는 다른 정점 C 를 거쳐가면

A 에서 B 로 가는 최단거리가 더 줄어 들 수 있느냐 이다.

 

플로이드 와샬 알고리즘의 특징은

음의 가중치를 갖는 그래프에서도 가능하며 (이때는 다익스트라 대신 사용가능)

음의 가중치에서 처리 가능한 벨만 포드 알고리즘에 비해서 시간복잡도가 우위에 있다는 특징이 있다.

 

- c++

 

#include <algorithm>
#include <iostream>
 
#define INF 1e9
#define MAX 100
 
using namespace std;
 
int n, m;
int dist[MAX][MAX];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> m;
    
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < n; ++j) 
            dist[i][j] = i == j ? 0 : INF;
 
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a - 1][b - 1] = min(dist[a - 1][b - 1], c);
    }
    
    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] == INF) cout << 0 << " ";
            else cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}