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

1. 행렬의 원소를 무한대로 설정한다.

2. 자기자신을 향하는 것을 의미하는 주대각원소들은 0으로 설정한다.

3. 간선을 입력 받는다.

4. a에서 b로 향하는 최단 거리는 a에서 k를 거쳐 b로 가는 경로중 가장 짧은 것을 찾아 설정한다.

#include <iostream>
#include <vector>
#include <queue>
#define endl '\n'
#define INF 1000000000 // 1e9
using namespace std;

int N, M;
int graph[101][101];

void input()
{
    cin >> N >> M;
    fill(&graph[0][0], &graph[100][101], INF);
    for (int i = 1; i <= N; i++)
        graph[i][i] = 0;

    for (int i = 0; i < M; i++)
    {
        int from, to, weight;
        cin >> from >> to >> weight;
        graph[from][to] = weight;
    }
}

void f_warshall()
{
    for (int k = 1; k <= N; k++)
    {
        for (int a = 1; a <= N; a++)
        {
            for (int b = 1; b <= N; b++)
            {
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
            }
        }
    }
}

void print()
{
    for (int a = 1; a <= N; a++)
    {
        for (int b = 1; b <= N; b++)
        {
            cout << graph[a][b] << " ";
        }
        cout << endl;
    }
}

int main(void)
{
    input();
    f_warshall();
    print();
    return 0;
}

시간복잡도 : O(N^3)

장점: 모든 노드에서 모든 노드로의 최단 거리를 알 수 있다.

단점: 노드가 많아지면 계산하는 데 매우 오래걸릴 수 있다.