플로이드 워셜

플로이드 워셜은 모든 점에서 다른 모든 점까지의 최소 거리를 구하는 알고리즘이다.

 

k라는 정점을 정해놓고 모든 점이 그 점을 경유했을 때 다른 모든 점까지의 최소값을 갱신하면서 모든 점 사이의 최소값을 구하는 방법이다. k를 모든 정점에 대해서 수행한다.

 

만약 i 정점에서 k까지 이어져 있지 않다면 j for문을 뛰어넘어도 상관이 없을 것이다.

 

const int MAX_V = 1000;

// 정점의 개수
int V;

// 간선이 없으면 아주 큰 값을 넣는다.
int adj[MAX_V][MAX_V];

void floyd() {
	for (int i = 0; i < V; i++) {
		adj[i][i] = 0;
	}

	for (int k = 0; k < V; k++) {
		for (int i = 0; i < V; i++) {
			for (int j = 0; j < V; j++) {
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
			}
		}
	}
}

 

최단 거리 경로

 

u와 v의 최단 경로를 경유하는 가장 큰점 k에 대해 w에 대해 u ~ w / w ~ v 를 재귀적으로 파고 들어가서 경로를 구한 후 합쳐준다.

// via[u][v] = u 에서 v까지 가는 최단 경로가 경유하는 점 중 가장 번호가 큰 정점
// 처음에 -1로 초기화
int via[MAX_V][MAX_V];

void floyd2() {
	for (int i = 0; i < V; i++) {
		adj[i][i] = 0;
	}

	memset(via, -1, sizeof(via));

	for (int k = 0; k < V; k++) {
		for (int i = 0; i < V; i++) {
			for (int j = 0; j < V; j++) {
				if (adj[i][j] > adj[i][k] + adj[k][j]) {
					via[i][j] = k;
					adj[i][j] = adj[i][k] + adj[k][j];
				}
			}
		}
	}
}

// u에서 v로 가는 최단 경로를 계산해 path에 저장한다.
// u에서 w까지의 거리와 w에서 v까지의 거리를 재귀적으로 구현
void reconstruct(int u, int v, vector<int>& path) {
	if (via[u][v] == -1) {
		path.push_back(u);
		if (u != v) path.push_back(v);
	}
	else {
		int w = via[u][v];
		reconstruct(u, w, path);
		path.pop_back(); // 중복으로 들어가기 때문에
		reconstruct(w, v, path);
	}
}