최단거리(2) 플로이드

최단거리(2) 플로이드

플로이드는 벨만 포드, 다익스트라와 다르게 모든 정점에서 다른 모든 정점까지의 거리를 구하는 방법입니다. 

 

일단 이전 다익스트라와 같이 Relax 함수가 핵심입니다. 

map[start][end] = min(map[start][mid] + map[mid][end], map[start][end]);

이렇듯 다른 정점을 거쳐서 가는 것이 더 빠르냐 아니면 바로 가는 것이 더 빠르냐 비교하여 작은 값을 넣는 것이 핵심입니다. 플로이드는 모든 출발 정점에서 도착 정점까지의 거리를 구하는 것임으로 n까지의 반복문을 3중으로 돌려야합니다.

 

sudo 코드

 

처음에 각 지점 별 weight를 저장한 후 weight가 없는 곳이라면 INF로 설정하겠습니다. 왜냐하면 초기에 0이면 min연산을 통해 값을 바꿀 수 없습니다. 

 

모든 출발점과 끝점과 함께 가운데 점을 모두 반복하여 최단 거리를 구해줍니다. 

 

https://www.acmicpc.net/problem/11404

11404번: 플로이드

#include <cstdio>
#include <algorithm>

using namespace std;

int INF = 987654321;
int n, m;
int map[102][102];

void input();
void floyd();

int main(){
	input();
	floyd();
	for(int i = 1; i <= n; i++){
		for(int y = 1; y <= n; y++){
			if(map[i][y] == INF)
				printf("0 ");
			else
			printf("%d ", map[i][y]);

		}
		printf("\n");
	}
}

void input(){
	int a, b, c;
	scanf("%d", &n);
	scanf("%d", &m);
	for(int i = 0; i < m; i++){
		scanf("%d %d %d", &a, &b, &c);
		if(map[a][b] == 0){
			map[a][b] = c;
		}
		else{
			map[a][b] = min(map[a][b], c);
		}
	}

	for(int y = 1; y <= n; y++){
		for(int x = 1; x <= n; x++){
			if(map[y][x] == 0)
				map[y][x] = INF;
		}
	}
}

void floyd(){
	for(int mid = 1; mid <= n; mid++){
		for(int start = 1; start <= n; start++){
			for(int end = 1; end <= n; end++){
				if(start != end)
				map[start][end] = min(map[start][mid] + map[mid][end], map[start][end]);
			}
		}
	}
}