플루이드 - 와샬 알고리즘

플루이드 - 와샬 알고리즘은 그래프 탐색 알고리즘중 가장 간단하지만 모든 정점사이의 최단거리를 구할 수있다.

하지만 시간 복잡도가 O(N^3) 이므로 정점의 갯수가 많으면 쓰는데 제약이있다.

 

설명보다는 문제를 보면서 이해하는게 쉽다.

 

문제 링크 : https://www.acmicpc.net/problem/11404

11404번: 플로이드

예제의 간선정보를 나타내보면

플루이드 와샬 알고리즘 적용전

적용전 배열에 플루이드 와샬 알고리즘을 적용 해보자

 

알고리즘

 

    //플로이드 와샬 알고리즘
 
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }

for 문 세개로 알고리즘이 끝이다 그래서 가장간단하다고 생각했다.

 

 

 

문제에 대한 전체 소스코드

 

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int N, M, map[101][101];
    cin >> N >> M;
 
    //배열 초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j)map[i][j] = 0;
            else map[i][j] = 1000000000;
        }
    }
 
    //간선 정보
    for (int j = 0; j < M; j++) {
        int a, b, c;
        cin >> a >> b >> c;
        map[a - 1][b - 1] = min(map[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++) {
                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == 1000000000) map[i][j] = 0;
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
    cout << endl;
       
 
 
}

 

플루이드 알고리즘은 가장 간단하지만 시간이 오래걸려  사용할  수 있는 문제가 제한적 이다.

그에비해 다익스트라 알고림즘은 다소 복잡하지만 최단거리를 더 빠른시간내에 구할 수있기에 보통 문제에

다익스트라 알고리즘을 많이 적용 한다.