[개념] 플로이드 와샬 (Floyd Warshall) / 백준 11404

 

'모든 정점' 에서 '모든 정점'으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야 한다.

플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다.

또한 플로이드 와샬은 기본적으로 다이나믹 프로그래밍(DP) 기술에 의거한다.

 

 

 

 

위와 같은 그래프가 존재한다고 해보자.

이때 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열의 형태로 출력하면 다음과 같다.

 

 

 

 

이제 이 테이블이 의미하는 바는 '현재까지 계산된 최소 비용' 이다. 

이러한 이차원 배열을 반복적으로 갱신하여 최종적으로 모든 최소 비용을 구하는게 목적이다.

바로 그러한 반복의 기준이 '거쳐가는 정점'인 것이다. 바로 1을 거쳐가는 경우부터 차례대로 살펴보도록 하자. 

(자기자신에서 출발하여 자기자신으로 도착하는 경우의 비용은 당연히 0이다.)

 

 

① 노드 1을 거쳐가는 경우

 

노드 1을 거쳐가는 경우는 위와 같이 6가지 공간만을 갱신해주면 된다. 이때 바로 다음의 두 식을 비교해주는 방식을 반복하는 것이다.

 

X에서 Y로 가는 최소 비용 VS X에서 노드 1로 가는 비용 + 노드 1에서 Y로 가는 비용

 

즉 1을 거쳐서 가는 경우가 더 빠른 경우가 존재한다면 그것으로 최소 비용을 대체하는 것이다.

예를 들어 D[2,3]의 값은 D[2,3]과 (D[2,1] + D[1,3]) 중에서 더 작은 값으로 교체된다. 따라서 노드 1을 거쳐가는 경우를 계산하면 다음과 같이 표가 구성된다.

 

 

 

 

② 노드 2를 거치는 경우

 

 

이때는 위와 같이 6가지 공간에 대해서만 계산을 진행하면 된다. 점화식은 동일하므로 처리 이후 다음과 같은 결과가 나온다.

 

왜 6가지 공간이 나오냐?

- 자기 자신으로 가는 경우들 1->1 , 2->2 ,....   갱신할 필요가 없음

- 2를 포함하는 경우들.. 2->1 , 2->2, 2->3, ... 이런 경우들은 갱신이 이루어지지 않는 부분들이기 때문에 확인할 필요가 없음

 

 

 

이제 위와 같은 방식으로 노드③, 노드④ 에 대해서도 수행해주면 된다.

그럼 결과적으로 다음과 같은 결과가 만들어진다.

 

 

 

 

이것을 코드로 적용해보면 다음과 같다.

 

#include <stdio.h>

int number = 4;
int INF = 10000000;

//자료 배열을 초기화 합니다.
int a[4][4] = {
	{0, 5, INF, 8},
	{7, 0, 9, INF},
	{2, INF, 0, 4},
	{INF, INF, 3, 0}
};

void floydWarshall() {

	// 결과 그래프를 초기화합니다.
	int d[4][4];

	// 결과 그래프를 초기화합니다.
	for (int i = 0; i < number; i++) {
		for (int j = 0; j < number; j++) {
			d[i][j] = a[i][j];
		}
	}

	// k = 거쳐가는 노드
	for (int k = 0; k < number; k++) {
		// i = 출발 노드
		for (int i = 0; i < number; i++) {
			// j = 도착 노드
			for (int j = 0; j < number; j++) {
				if (d[i][k] + d[k][j] < d[i][j]) {
					d[i][j] = d[i][k] + d[k][j];
				}
			}
		}
	}
}

int main(void) {
	floydWarshall();
}

 

 

 

 

---

백준 11404. 플로이드

분류 - 그래프 알고리즘

 

 

위의 플로이드 와샬 알고리즘을 적용하면 쉽게 풀 수 있다.

 

#include <iostream>
#include <algorithm>

using namespace std;
const int MAX = 100 + 1;
const int INF = 100000 + 1;

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

void floyd(void)
{

    // via번째 도시를 거쳐가는게 더 빠를 경우 update
    for (int via = 1; via <= N; via++)
    {
        for (int from = 1; from <= N; from++)
        {
            // from 부터 거쳐가는 다리까지의 경로가 없는 경우는 셀 필요도 없으므로
            if (graph[from][via] == 0)
                continue;

            for (int to = 1; to <= N; to++)
            {
                // 거쳐가는 다리부터 to까지의 경로가 없는 경우 or  
                // 출발지점과 도착지점이 같은 경우는 셀 필요가 없으므로 
                if (graph[via][to] == 0 || from == to)
                    continue;

                // graph[from][to] == 0 인 경우는 경로가 없다는 거니깐, 무조건 거쳐가는 경로를 넣어주어야 한다 
                if (graph[from][to] == 0 || graph[from][to] > graph[from][via] + graph[via][to])
                    graph[from][to] = graph[from][via] + graph[via][to];
            }
        }
    }
}

int main(void)
{
    cin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        int from, to, cost;
        cin >> from >> to >> cost;

        if (!graph[from][to])
            graph[from][to] = cost;

        else //이미 경로가 있는 경우 최소값 선택  - 문제에 보면 시작 도시와 도착 도시를 연결하는 노선은 하나 이상일 수 있다고 되어있음.
            graph[from][to] = min(graph[from][to], cost);
    }

    floyd();

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
            cout << graph[i][j] << " ";

        cout << "\n";
    }
    return 0;
}

 

 

그런데, 시간복잡도를 더 줄일 수 있을까 싶어서 다음과 같이

출발 지점 (from) == 거처가는 지점 (via) 인 경우, 

거처가는 지점 (via) == 도착 지점 (to) 인 경우

이 두 경우는 갱신할 필요조차 없으므로 다음과 같이 continue 조건에 넣어 주어 보았다.

 

 if (graph[from][via] == 0 || from == via)
    continue;
    
    ...
    
    if (graph[via][to] == 0 || from == to || via == to)
      continue;

 

 

그래도 시간은 똑같이 나왔다

 

 

 

 

 

 

 

 

 

출처

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https%3A%2F%2Fwww.google.com%2F

https://jaimemin.tistory.com/595