なぜfloodとshallアルゴリズムを使うのか

すべての頂点からすべての頂点までの最短距離を検索します.
参照として、マルチアウトアルゴリズムは、1つの頂点からすべての頂点までの最短距離を検索するために使用されます.

フロイドとシエル

を通過した頂点を基準に行います.

DPの一種で、2次元配列を採用している.

を通過する頂点がより効率的であるか、より効率的でないかを比較することによって、DPアレイにより効率的に格納される.

初期DPアレイ初期化時(1,1)、自身を先頭としてノードに到達した場合はその値を0とし、直接行けない場合は無限にINFに初期化する.この場合、INFを実整数の最大値として21億とすると、以降の計算中にINF+xがオーバーフローして負数となり、正常な比較ができなくなるので、10,000,000,000程度まで十分な大きさであることに注意すべきであるが、ある数を加えればオーバーフローしない.

floydとshallアルゴリズムコード

// 자기 자신을 시작, 도착 노드인 경우 0으로 DP 배열을 초기화
// 바로 갈 수 없는 경우 INF로 DP 배열을 초기화
//n은 정점의 개수
void floyd_warshall(int n) {
	// k : 거처가는 정점
	for (int k = 1; k <= n; k++) {
		// i : 시작 정점
		for (int i = 1; i <= n; i++) {
			// j : 도착 정점
			for (int j = 1; j <= n; j++) {
				if (dp[i][k] + dp[k][j] < dp[i][j]) { //k를 거처가는 것이 비용이 덜 든다면 값 갱신
					dp[i][j] = dp[i][k] + dp[k][j];
				}
			}
		}
	}
}

参考例

白駿11404号フロイド

📝 質問する

📌 に答える

は、すべてのパスを無限に初期化します.

自身から、着いたら距離を0にリセットします.

開始-到着路線と料金を入力し、同じ路線の複数のバスがあれば最小値のみ初期化します.

フロイド・マーシャルアルゴリズムを実行します.

の結果DP配列が出力され、このときもINF値があると歩けないので0が出力される.

💻 コード#コード#

//난이도 : 골드4
//시작 : 09:26
//끝 : 09:46
#include <iostream>
#include <limits>

using namespace std;

#define INF 100000000 //무한 값 정의

int dp[101][101] = { 0 };

//n은 정점의 개수
void floyd_warshall(int n) {
	// k : 거처가는 정점
	for (int k = 1; k <= n; k++) {
		// i : 시작 정점
		for (int i = 1; i <= n; i++) {
			// j : 도착 정점
			for (int j = 1; j <= n; j++) {
				if (dp[i][k] + dp[k][j] < dp[i][j]) { //k를 거처가는 것이 비용이 덜 든다면 값 갱신
					dp[i][j] = dp[i][k] + dp[k][j];
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//모든 경로를 무한으로 초기화
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < 101; j++) {
			dp[i][j] = INF;
		}
	}

	int n, m;
	cin >> n >> m;

	//자기 자신을 시작, 도착으로 가지면 거리는 0이다.
	for (int i = 1; i <= n; i++) {
		dp[i][i] = 0;
	}

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (dp[a][b] > c) { // 최소 거리만 갱신 //같은 구간을 연결하는 노선이 하나가 아닐 수 있기 때문
			dp[a][b] = c;
		}
	}

	// 플로이드-마샬 알고리즘 수행
	floyd_warshall(n);

	//결과 출력
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i][j] == INF) { //여전히 갈 수 없는 경우
				dp[i][j] = 0; //0으로 출력
				cout << dp[i][j] << " ";
			}
			else {
				cout << dp[i][j] << " ";
			}
		}
		cout << '\n';
	}


	return 0;
}

参考資料

眼鏡師開発者-実戦アルゴリズム講座