[알고리즘] 플로이드-워셜(Floid-Warshall) 알고리즘

※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다.

 

※ 해당 포스팅은 하기 출처들을 참조하였습니다.

- 존 캐리, 코딩 테스트를 위한 자료구조와 알고리즘 with C++, 도서출판 길벗, 2022

- https://chanhuiseok.github.io/posts/algo-50/

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

https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm

 

 

 

1. 플로이드-워셜 알고리즘

 플로이드-워셜 알고리즘은 모든 노드에서 각 노드까지의 최단 거리를 구하는 알고리즘입니다. 정점 A에서 B까지의 최단거리를 (A → B)라 하고, 정점 B에서 C 까지의 거리를 (B → C)라 한다면 A에서 C까지의 최단 거리는 (A → B) + (B → C) 라는 논리를 기본 바탕으로 합니다. 그리고 A에서 C까지 직접 연결되어 있을 수도 있으므로, 결과적으로는 (A → B) + (B → C)와 (A → C) 중 작은 값을 취합니다.

 

 플로이드-워셜 알고리즘을 구현할 때는 3중 반복문을 사용하게 됩니다. 위 문단의 예시를 이용하자면 그래프의 모든 노드에 대해서 (A → C)의 값을 (A → B) + (B → C)와 (A → C) 중 작은 값으로 갱신하는 과정을 반복합니다. 즉, 정점의 개수가 n이라고 한다면 O(n^3)의 시간복잡도로 구현됩니다. 밑에서 소개하겠지만 3중 반복문을 사용하는 대신 구현 자체는 굉장히 단순합니다. 대신 그래프에 음수 가중치가 존재한다면, 음수 사이클에 대한 검사 과정을 추가해주어야 합니다.

 

 플로이드-워셜 알고리즘을 적용하는 과정은 다음과 같습니다.

사진 1. 그래프 예시

 

  사진 1은 노드가 5개인 그래프와 노드들의 연결 정보를 2차원 행렬에 기록한 모습입니다. 자기 자신으로의 거리는 0으로 초기화하고, 노드의 연결 정보(비용)를 기록합니다. 나머지 칸은 해당 노드간의 직접적인 간선이 존재하지 않는 경우이므로, 두 노드간의 비용을 더한 값보다 항상 크도록 아주 큰 값으로 초기화합니다. 

 

사진 2. 0번 노드를 경유하는 경로 갱신

 

 그리고 0번 노드부터 시작하여 해당 노드를 경유하여 가는 경로를 갱신합니다. 위 예시의 경우 1번 노드에서 2번 노드로, 2번 노드에서 1번 노드로 가는 경로가 3 + 5 = 8로 초기값(아주 큰 값)보다 작으므로 8로 갱신한 모습입니다. 위 과정을 모든 노드에 대해 반복하면 다음과 같은 결과를 얻을 수 있습니다.

 

사진 3. 모든 경로 갱신 후

 

 주목할 만한 부분은 0번 노드에서 4번 노드로 가는 비용을 계산하는 부분입니다. 처음에는 1번 노드를 경유하는 비용 17로 저장되었지만, 이후에 2번 노드를 경유하는 비용 7짜리 경로로 다시 갱신되고 있습니다. 이렇듯 처음에는 비용이 높은 경로로 갱신되기도 하지만, 모든 노드를 경유하는 케이스를 검사하여 최종적으로는 비용이 가장 적은 경로를 찾게 됩니다.

 

 시간복잡도가 세제곱인 것을 고려하면 굉장히 비효율적인 알고리즘 같지만, 고려사항이 오로지 노드의 개수 뿐이라는 점에서 해당 알고리즘을 사용하기 적합한지 판단하기 쉽다는 장점이 있습니다. 또한 노드의 수가 적고 간선이 많은 밀집 그래프에서는 생각보다 효율이 좋게 나올 수 있습니다. 예를 들어 노드가 100개인 그래프의 경우 간선의 숫자가 최대 4950개 나올 수 있으며(n * (n - 1) / 2), 이렇게 밀집된 그래프라면 간선의 갯수가 영향을 미치는 알고리즘의 효율성이 떨어집니다. 하지만 플로이드-워셜 알고리즘이라면 단순히 100 ^ 3 = 1,000,000회의 연산이 필요하고 비교적 괜찮은 선택지가 될 수 있습니다.

 

 

2. 코드 예시 

 다음은 노드의 갯수, 간선 정보를 입력 받은 뒤 플로이드-워셜 알고리즘을 통해 모든 노드에서의 최소 거리를 구하는 C++ 코드 예시입니다.

#include <iostream>
#include <vector>

using namespace std;

bool floyd_warshall(const int n, const vector<vector<int>>& edges, vector<vector<int>>& result)
{
    // 자기 자신과의 거리는 0으로 초기화
    for (int i = 0; i < n; ++i)
        result[i][i] = 0;

    // 간선 정보 입력
    for (const vector<int>& edge : edges)
    {
        result[edge[0]][edge[1]] = edge[2];
        result[edge[1]][edge[0]] = edge[2];
    }

    // 플로이드-워셜 알고리즘
    for (int mid = 0; mid < n; ++mid)
        for (int start = 0; start < n; ++start)
            for (int end = 0; end < n; ++end)
                result[start][end] = min(result[start][end], result[start][mid] + result[mid][end]);

    // 자기 자신으로의 거리가 0보다 작다면 음수 사이클이 발생한 것 -> false 반환
    for(int i = 0; i < n; ++i)
    {
        if (result[i][i] < 0)
        {
            return false;
        }
    }

    return true;
}

int main()
{
    int n;
    cout << "노드의 갯수를 입력해주세요: ";
    cin >> n;

    vector<vector<int>> edges;
    cout << "노드의 연결 정보를 입력해주세요 - 시작 노드, 도착 노드, 비용 순서로\n(스페이스바로 구분, -1 입력 시 종료)\n";
    while(true)
    {
        int start, end, cost;
        cin >> start;
        if (start == -1) break;
        cin >> end >> cost;
        
        edges.push_back(vector<int>{start, end, cost});
    }
    cout << "\n";

    // 간선 정보를 저장할 2차원 벡터 선언
    // 초기값은 데이터를 고려하여 어느정도 큰 값으로 선언
    vector<vector<int>> result(n, vector<int>(n, 10000000));
    if(false == floyd_warshall(n, edges, result))
    {
        cout << "음수 사이클이 발생했습니다.\n";
        return 0;
    }

    // 결과 출력
    for(int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cout << result[i][j] << " ";
        }
        cout << "\n";
    }
}

사진 4. 예제 코드 실행 결과

 

 사진 4는 사진 1의 예시 그래프 정보를 입력하여 결과를 출력한 모습입니다. 플로이드-워셜 알고리즘의 핵심인 비용 갱신 부분은 사실상 3중 반복문을 4줄이 전부일 정도로 단순한 것을 볼 수 있습니다. 해당 예시의 경우에는 비용에 음수가 들어가지 않았지만, 음수가 들어가는 경우에는 상기 코드와 같이 3중 반복문 실행 후 음수 사이클의 존재 여부를 검사할 필요가 있습니다. 자기 자신으로의 비용이 0보다 작아졌다면 음수 사이클이 발생한 것이고, 이는 해당 알고리즘을 적용할 수 없다는 의미이므로 false를 반환하도록 했습니다. 

 

 

3. 관련 문제

 코딩 테스트 연습 중에 해당 알고리즘을 사용하여 풀기 좋은 문제를 발견했습니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

 

 해당 문제에서 총 합승 요금은 [시작 노드부터 i번 노드까지의 요금(합승 구간)] + [i번 노드부터 A의 집까지의 요금] + [ i번 노드부터 B의 집까지의 요금] 입니다. 플로이드-워셜 알고리즘을 사용하고 나면 모든 노드에서 다른 노드까지의 최소 거리가 나오므로, 반복문을 통해 모든 노드를 대상으로 총 합승 요금을 구한 뒤 가장 작은 값을 반환하면 됩니다.

 

 다만, 요금 정보를 저장하는 2차원 벡터의 초기값을 정할 때 주의해야 합니다. 우선 최대값이라고 해서 numeric_limits<int>::max()와 같은 값을 사용하면, (A → B) + (B → C)를 계산하는 과정에서 오버플로우가 일어날 수 있습니다. 만약 몇몇 테스트 케이스에서 결과값에 음수가 나온다면, 그래프의 초기값을 의심해보아야 합니다. 또한 너무 작은 값을 주어도 안됩니다. 문제 조건에서 그래프 가중치의 최대값을 100,000으로 주고 있는데, 이를 보고 100,001과 같은 값을 주면 마찬가지로 (A → B) + (B → C)의 값이 초기값을 넘어가는 상황이 발생할 수 있으므로 적당히 큰 값을 주어야 합니다. 저는 해당 문제 기준으로는 1,000,000 정도 주어서 해결했습니다.