[알고리즘/C++] 플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드 워셜(Floyd-Warshall) 알고리즘은 거리 정보를 담는 행렬을 이용하여

 

모든 노드 간의 최단 경로를 구하는 알고리즘이다. 

 

void floydWarshall(vector<vector<int>>& distance, vector<vector<pair<int, int>>> adj) {
	for (int i = 0; i < distance.size(); i++) {
		for (int j = 0; j < distance.size(); j++) {
			if (i == j) {
				distance[i][j] = 0;
			}
			else {
				distance[i][j] = 100;
			}
		}
	}

	for (int i = 1; i < adj.size(); i++) {
		for (int j = 0; j < adj[i].size(); j++) {
			distance[i][adj[i][j].first] = adj[i][j].second;
		}
	}

	for (int k = 1; k < adj.size(); k++) {
		for (int i = 1; i < adj.size(); i++) {
			for (int j = 1; j < adj.size(); j++) {
				if (distance[i][j] > distance[i][k] + distance[k][j]) {
					distance[i][j] = distance[i][k] + distance[k][j];
				}
			}
		}
	}
}

전체 코드는 위와 같다.

	for (int i = 0; i < distance.size(); i++) {
		for (int j = 0; j < distance.size(); j++) {
			if (i == j) {
				distance[i][j] = 0;
			}
			else {
				distance[i][j] = 100;
			}
		}
	}

먼저 distance 행렬의 대각 성분을 0으로, 나머지 요소들을 임의의 큰 값으로 초기화한다. 

 

distance[start][end] = 8 이라는 의미는 start 노드에서 end 노드까지의 거리가 8이라는 의미이다.

 

이 요소에 알고리즘을 통해서 최단 거리를 담아내야한다. 

	for (int i = 1; i < adj.size(); i++) {
		for (int j = 0; j < adj[i].size(); j++) {
			distance[i][adj[i][j].first] = adj[i][j].second;
		}
	}

처음에는 인접 리스트의 정보를 통해서 직접 이웃의 노드의 가중치를 초기 거리로 갱신한다. 

 

직접 이웃한 노드가 아니라면 해당 요소의 정보 업데이트는 이루어지지 않는다. 

	for (int k = 1; k < adj.size(); k++) {
		for (int i = 1; i < adj.size(); i++) {
			for (int j = 1; j < adj.size(); j++) {
				if (distance[i][j] > distance[i][k] + distance[k][j]) {
					distance[i][j] = distance[i][k] + distance[k][j];
				}
			}
		}
	}

distance의 각 요소에는 노드 a(행) 에서 노드 b(열) 까지의 거리 정보를 담고 있으므로 

 

중간 노드 k를 거쳐서 더 가까워질 수 있으면 k를 경유한 더 짧은 길이로 갱신한다. 

 

행렬 전체를 순회하는 과정이 노드의 갯수만큼(중간 노드로 선정 가능한 경우의 수)의 횟수만큼 반복된다. 

 

시간 복잡도는 O(n^3)이므로 그래프의 크기가 짧은 경우에만 사용하는 것이 좋다.

 

void initGraph2(vector<vector<pair<int,int>>>& adj) {
	adj.push_back({ {0, 0} });
	//sentinel node
	adj.push_back({ {2, 5}, {4, 9}, {5, 1} });
	adj.push_back({ {1, 5}, {3, 2} });
	adj.push_back({ {2, 2}, {4, 6} });
	adj.push_back({ {1, 9}, {3, 6}, {5, 2} });
	adj.push_back({ {1, 1}, {4, 2} });
}

그래프의 최초 생성하는 함수이다.

	vector<vector<pair<int, int>>> adj;
	//each node has several (neighbor, weight) pair.
	initGraph2(adj);
	//make adjacent matrix

	vi temp(6, 0);
    //노드의 갯수가 5개. 보초값 1개 추가.

	vector<vi> distance(6, temp);

	floydWarshall(distance, adj);

	print2DVec(distance);

0 100 100 100 100 100
100 0 5 7 3 1
100 5 0 2 8 6
100 7 2 0 6 8
100 3 8 6 0 2
100 1 6 8 2 0

//첫 행과 첫 열은 sentinel value