플로이드-워셜 알고리즘(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

결과 1

입력 2

결과 2

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

728x90

그리드형(광고전용)

저작자표시 비영리

'Computer Science > Algorithm' 카테고리의 다른 글

팩토리얼(Factorial) (0)	2022.08.31
완전수(Perfect Number), 부족수(Deficient Number), 과잉수(Abundant Number) (0)	2022.08.31
가우스 계산법(Gaussian Calculation) (0)	2022.08.31
부분집합의 합 문제(Subset Sum Problem) (0)	2021.07.22
코사라주 알고리즘(Kosaraju's Algorithm) (0)	2021.07.04
존슨 알고리즘(Johnson's Algorithm) (0)	2021.07.04
벨만-포드 알고리즘(Bellman-Ford Algorithm) (0)	2021.07.02
다익스트라 최단 경로 알고리즘(Dijkstra Shortest Path Algorithm) (0)	2021.06.30