플로이드-워셜

플로이드-워셜은 다익스트라를 각 정점에 대해 1번씩 즉, N번 한거라고 생각하면 된다.

 

근데 이때 진짜로 다익스트라를 N번 사용하는건 아니고

모든 정점 간의 최단거리를 알기 위해 dp로 다익스트라를 N번을 돌린 결과를 만들어준다.

 

5
7
2 4 3
3 4 5
1 2 4
1 5 10
4 5 2
1 3 2
3 2 1

 

플로이드 워셜 알고리즘은 다익스트라 알고리즘과 목적이 비슷하다.
어떻게 보면 다익스트라보다 확장된 개념이다.
 
다익스트라는 특정한 한 정점에서 모든 정점까지의 최소 cost를 구하는 것이라면
플로이드워셜은 모든 정점 간의 최소 cost를 구하는 것이다.
즉 해당 그래프 내 모든 노드에 대한 최소거리를 구하는 알고리즘이라고 생각하면 된다.
 

다익스트라는 priority queue를 이용하여 greedy로 접근한다면
플로이드워셜은 2차원 배열을 이용하여 dp방식으로 접근한다.

매번 최소거리를 구하지 않고 이미 구해놓은 최소거리를 이용하는 방식인 것이다
 
floyd-warshall의 코드 상에서의 목적은 2차원 dp배열을 모두 채우는 거임
 
여기서 각 dp칸은 즉 dp[i][k]는 정점 i에서 정점 k로 갈때의 최소 비용을 의미하는 것이다.
즉, i에서 k로 가는 것에 대한 다익스트라 알고리즘의 결과라고 보면 된다.
 
그니까 정점이 만약 N개이면 플로이드워셜은 다익스트라를 N^2번 한거라고 생각하면 된다.
 

---

 [플로이드 워셜 로직]

    // 플로이드 워셜로 모든 정점에서 모든 정점까지의 최단거리 구하기
    for (int mid = 1; mid <= V; mid++)
    {
        for (int start = 1; start <= V; start++)
        {
        	// start와 mid가 동일하면 스킵
            // start에서 mid로 갈 수 없으면 스킵
            if (start == mid || dp[start][mid] == INF)
            {
                continue;
            }

            for (int end = 1; end <= V; end++)
            {
            	// mid와 end가 동일하면 스킵
                // mid에서 end로 갈 수 없으면 스킵
                if (end == mid || dp[mid][end] == INF)
                {
                    continue;
                }

                // start에서 end로 갈 수 있는거리 최신화
                dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid][end]);
            }
        }
    }

플로이드 워셜은 생각보다 굉장히 간단하다.
3중for문을 돌리면 답이 나오기 때문인데
여기서 중요한게 가장 바깥쪽 for문이 거쳐가는 중간노드를 기준으로 한다는 것이다.
 
즉 3중for문 형식이 아래와 같다.

for 중간노드
	for 시점노드
    		for 종점노드
        		dp[시작][끝] = min(dp[시작][끝], dp[시작][중간] + dp[중간][끝])

 
초기세팅은 일단 모두 INF로 초기화한다.
그리고 시작과 끝이 같은 경우는 0으로 초기화해놓는다.

간선 정보를 해당 dp 배열에 입력한 뒤 플로이드워셜 3중포문을 돌리면 된다.

 

---

따로 vector<vector<int>> graph(SIZE)로 그래프로 간선 정보를 나타내줄 필요가 없다.

어차피 간선 정보가 다 dp 배열에 입력되어있기 때문이다.

 

#include <iostream>
#include <algorithm>

#define INF int(1e9)
#define SIZE 101

using namespace std;

int dp[SIZE][SIZE];

// d[a->b] = d[a->k] + d[k->b];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, M;
	cin >> N >> M;

	// dp 초기화
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			dp[i][k] = INF;
		}
	}
    
    // i에서 i로의 거리는 0
	for (int i = 1; i <= N; i++) { dp[i][i] = 0; }

	// init dp by input
	int start, end, cost;
	for (int i = 0; i < M; i++) {
		cin >> start >> end >> cost;
		if(dp[start][end] > cost) dp[start][end] = cost;
	}

	// 플로이드 워셜
	for (int mid = 1; mid <= N; mid++) {
		for (start = 1; start <= N; start++) {
        	if(dp[start][mid] == INF) continue;
            
			for (end = 1; end <= N; end++) {
				dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid][end]);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			cout << dp[i][k] << " ";
		}
		cout << "\n";
	}
	return 0;
}