[Algorithms] Floyd-Warshall Algorithm | 플로이드-워샬 알고리즘

Floyd-Warshall Algorithm

플로이드-워샬 알고리즘

- 그래프 상에서, 존재할 수 있는 모든 (출발 정점, 도착 정점) Pairs에 대한 최단 경로를
  Dynamic Programming 기법을 적용하여 계산해내는 알고리즘이다.
- Warshall이 Directed Graph에서 정점들 간의 상호 연결 경로의 존재 여부를 밝히는 알고리즘을 제안하고,
  Floyd가 이를 변형하여 최단 경로를 찾아내는 알고리즘으로 만들었다.
  (즉, Warshall의 기여가 더 크다.)

* Graph (그래프) (URL)

[Data Structures] Graph | 그래프

---

Mechanism (원리)

※ 이 문제의 최적해는 Optimal Substructure를 갖고 있으므로, Dynamic Programming (URL) 기법을 적용해 볼 수 있다.

[Algorithms] Dynamic Programming (DP) | 동적 프로그래밍

\(w_{ij}\) : 정점 \(i\)에서 정점 \(j\)까지의 가중치

\(d_{ij}^{k}\) : 정점 집합 \(\{1, 2, \cdots, k\}\)에 속하는 정점들만 중간 정점으로 거쳐서 \(i\)에서 \(j\)에 이르는 최단 거리
(즉, 여기서 \(k\)는 \(i\)에서 \(j\)까지의 경로 중 거치는 중간 정점의 개수이다.)

\(d_{ij}^{k} = 
\begin{cases}
w_{ij} \qquad \qquad \qquad \qquad \qquad \qquad \quad \mathrm{(if} \; k=0\mathrm{)}\\\\
\mathrm{min}\{d_{ij}^{k-1}, d_{ik}^{k-1}+d_{kj}^{k-1}\} \qquad \qquad \; \mathrm{(if} \; k\geq 1\mathrm{)}
\end{cases}
\)

- \(d_{ij}^{k}\)를 계산할 때, 위 그림처럼 두 가지 선택지 중, 경로가 더 짧은 하나를 골라야 하는 상황이 발생한다.
- \(p\)는 정점 \(i\)에서 정점 \(j\)로 향하는 경로이다.를 \(p\)라 하자.

Case 1) 경로 \(p\)에 정점 \(k\)가 포함되어야 하는 경우 (그림의 위쪽 경로)
- 정점 \(k\)를 중심으로, 경로 \(i \rightsquigarrow k\)와 경로 \(k \rightsquigarrow j\) 로 나누어볼 때,
  최단 경로상에 사이클은 존재할 수 없으므로, 두 경로의 중간에 정점 \(k\)는 더 이상 나타나지 않아야 한다.
- 즉, 이 두 경로는 각각 정점 집합 \(\{1, 2, \cdots, k-1\}\)에 속하는 정점들만을 거치는 최단 경로 \(i \rightsquigarrow k\)와
  정점 집합 \(\{1, 2, \cdots, k-1\}\)에 속하는 정점들만을 거치는 최단 경로 \(k \rightsquigarrow j\)가 되고,
  이 두 경로의 길이는 각각 \(d_{ik}^{k-1}\)과 \(d_{kj}^{k-1}\)가 된다.

Case 2) 경로 \(p\)에 정점 \(k\)가 포함되어 있지 않아야 하는 경우 (그림의 아래쪽 경로)
- 이 경우, 최단 경로는 정점 집합 \(\{1, 2, \cdots, k-1\}\)에 속하는 정점들만을 거치게 되므로,
  \(d_{ij}^{k} = d_{ij}^{k-1}\)가 된다.
  (즉, 정점 \(k\)가 있건 없건 최단 경로상에 변화를 주지 못한다.)

---

Implementation (구현)

* GitHub (URL)

* Pseudo Code

floyd_warshall(G)
// G = (V, E) : Given Graph
// w(a, b) : Weight from vertex 'a' to 'b' ('a' and 'b' must be adjacent)
// n : # of Vertices
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            d_{ij}^{0} = w(i, j);
            
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                d_{ij}^{k} = min( d_{ij}^{k-1}, d_{ik}^{k-1} + d_{kj}^{k-1} );
}

* C++ (Based on BOJ 11403 (URL))

// Headers
#include <iostream>
using namespace std;


// Alisaes
typedef int type;
typedef unsigned int u_type;

const type V_MAX = 100;    // Max of # of vertices
u_type N;                  // # of vertices
type graph[V_MAX][V_MAX];  // Original Graph
type s_dist[V_MAX][V_MAX]; // Distance of shortest path

const type DISCONNECTED = 0; // Symbol of disconnection
const type W_MAX = V_MAX+1;  // Max of weight


// Functions
void process_input();
void calc_by_FW(); // Calculate by Floyd-Warshall Algorithm
void process_output();

type max(type a, type b) { return (a < b ? b : a); }


// Implementation
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    process_input();
    calc_by_FW();
    process_output();

    return EXIT_SUCCESS;
}

void process_input()
{
    cin >> N;

    type weight;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> weight;
            graph[i][j] = weight;
            s_dist[i][j] = weight;

            if (weight == DISCONNECTED)
                s_dist[i][j] = W_MAX;
        }
    }
}

void calc_by_FW()
{
    for (int k = 0; k < N; k++)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                s_dist[i][j] = min(s_dist[i][j], s_dist[i][k] + s_dist[k][j]);
            }
        }
    }
}

void process_output()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (s_dist[i][j] != W_MAX)
                cout << "1 ";
            else
                cout << "0 ";
        }
        cout << '\n';
    }
}

---

Performance (성능)

Time Complexity : \(\Theta(|V|^3)\)

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)