플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

• 모든 쌍 최단 경로(All-Pairs Shortest Path)를 구하는 알고리즘
• O(V³)의 시간 복잡도와 O(V²)의 메모리 사용량으로 동작하는 상향식 알고리즘
• 벨만-포드 알고리즘
  • 그래프의 두 정점 사이의 최단 경로가 출발 정점에서 시작하는 다른 최단 경로와 최종 목표 정점으로 연결된 에지의 조합으로 구성됨.
• 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 은 이러한 개념에 좀 더 광범위한 일반화를 적용함으로써 큰 효과를 얻음.
  • 정점 A와 정점 B 사이의 최단 거리가 AB이고, 정점 B와 정점 C 사이의 최단 거리가 BC이면, 정점 A와 정점 C 사이의 최단 거리는 AB + BC 임.
    • 이 논리는 그 자체로 획기적인 것은 아님.
      • 이 논리와 (V - 1)번의 반복을 통해 최단 거리를 구하는 벨만-포드 알고리즘 을 결합하여 사용할 수 있음.
        • 먼저 정점 A에서 나머지 모든 정점까지의 최단 경로를 구하고, 이 결과를 이용하여 점진저으로 정점 B, C, D 등에서 시작하는 잠재적인 최단 경로를 구할 수 있음.
• 플로이드-워셜 알고리즘은 정점들에 대해 V³만큼 반복하여 결과를 얻을 수 있음.
  • 첫 번째 차원 : A 정점과 C 정점 사이에 있는 정점 B
• 이 알고리즘은 현재까지 구한 A에서 C까지의 거리가 A에서 B까지의 거리와 B에서 C까지의 거리를 합한 값보다 큰지를 검사함.
  • 만약 그렇다면, 해당 합계가 A에서 C까지의 최적의 최단 거리에 더 적합하기 때문에 이 값을 캐시 테이블 에 저장함.
• 플로이드-워셜 알고리즘은 그래프의 모든 정점을 중간 정점 으로 사용하면서 지속적으로 결과 정확도를 향상시킴.
  • 모든 정점을 시작 정점 과 목표 정점 으로 사용하고, 동시에 모든 정점을 중간 정점 으로 사용하면서 테이블에는 모든 정점 쌍 사이의 최단 거리가 저장됨.
• 다른 그래프 알고리즘과 마찬가지로 플로이드-워셜 알고리즘도 모든 상황에서 최선의 선택이라고 보장할 수 없음.
  • 다른 대안 알고리즘과 복잡도를 고려해봐야 함.
• 일반적으로 많은 수의 에지로 구성 되어 있는 밀집 그래프(Dense Graph) 에서는 플로이드-워셜 알고리즘을 사용하는 것이 좋음.
  • 예) 100개의 정점과 500개의 에지가 있는 그래프
    • 벨만-포드 알고리즘
      • 최악의 경우 O(V x E)의 복잡도를 갖음.
        • 각각의 정점을 시작 정점으로 취급해서 실행하면 100 x 100 x 500 = 5,000,000 번의 연산이 필요함.
    • 플로이드-워셜 알고리즘
      • 100 x 100 x 100 = 1,000,000 번의 연산이 필요함.
• 다익스트라-알고리즘 은 보통 벨만-포드 알고리즘보다 더 효율적이며, 대안으로 사용할 수도 있음.
  • 그럼에도 플로이드-워셜 알고리즘이 가지고 있는 뚜렷한 장점은 다른 그래프 특성에 상관 없이 전체 복잡도가 항상 O(V³) 라는 점
    • 플로이드-워셜 알고리즘이 얼마나 효율적으로 동작할 것인지를 가늠하기 위해서는 오직 그래프의 정점 개수만 알면 됨.
• 플로이드-워셜 알고리즘도 음수 에지 가중치가 있는 그래프에서 동작함.
  • 음수 에지 사이클에 대해서는 별도의 처리를 수행해야 함.

 

코드

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

const int UNKNOWN = 1e9;

vector<vector<int>> FloydWarshall(int V, vector<vector<int>> weight) {
    vector<vector<int>> distance(V, vector<int>(V, UNKNOWN));
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            distance[i][j] = weight[i][j];
        }
        distance[i][i] = 0;
    }

    for (int mid = 0; mid < V; mid++) {
        for (int start = 0; start < V; start++) {
            for (int end = 0; end < V; end++) {
                if (distance[start][mid] + distance[mid][end] < distance[start][end]) {
                    distance[start][end] = distance[start][mid] + distance[mid][end];
                }
            }
        }
    }

    for (int i = 0; i < V; i++) {
        // 자기 자신으로의 거리가 0보다 작으면 음수 가중치 사이클이 있는 것으로 판단.
        if (distance[i][i] < 0) {
            return {};
        }
    }

    return distance;
}

int main() {
    int V, E;

    cin >> V >> E;

    vector<vector<int>> weight(V, vector<int>(V, UNKNOWN));

    for (int i = 0; i < E; i++) {
        int u, v, w;

        cin >> u >> v >> w;

        weight[u][v] = w;
    }

    vector<vector<int>> distance = FloydWarshall(V, weight);

    if (distance.empty()) {
        cout << "음수 가중치 사이클이 있습니다." << endl;
        return 0;
    }

    for (int i = 0; i < V; i++) {
        cout << i << endl;

        for (int j = 0; j < V; j++) {
            cout << "\t" << j << ": ";

            (distance[i][j] == UNKNOWN) ? cout << "_" << endl : cout << distance[i][j] << endl;
        }
    }

    return 0;
}

 

결과

입력 1

7 9
0 1 3 
1 2 5 
1 3 10
1 5 -4
2 4 2 
3 2 -7
4 1 -3
5 6 -8
6 0 12
0

 

결과 1

0
        0: 0
        1: 3
        2: 6
        3: 13
        4: 8
        5: -1
        6: -9
1
        0: 0
        1: 0
        2: 3
        3: 10
        4: 5
        5: -4
        6: -12
2
        0: -1
        1: -1
        2: 0
        3: 9
        4: 2
        5: -5
        6: -13
3
        0: -8
        1: -8
        2: -7
        3: 0
        4: -5
        5: -12
        6: -20
4
        0: -3
        1: -3
        2: 0
        3: 7
        4: 0
        5: -7
        6: -15
5
        0: 4
        1: 7
        2: 10
        3: 17
        4: 12
        5: 0
        6: -8
6
        0: 12
        1: 15
        2: 18
        3: 25
        4: 20
        5: 11
        6: 0

 

입력 2

6 8
0 1 3
1 3 -8
2 1 3
2 4 2
2 5 5
3 2 3
4 5 -1
5 1 8

 

결과 2

음수 가중치 사이클이 있습니다.