ChienI Kao

筆記網站

JHTNT

筆記網站

# 題目

Floyd-Warshall 演算法 wiki
撰寫出 Floyd-Warshall 演算法，處理點到點的最短路徑

# 單機版程式

	#include <bits/stdc++.h>
	#define N 1000
	using namespace std;

	int main() {
	srand(36);

	long start = clock();
	int **D;
	D = (int *)malloc(N sizeof(int *));
	for (int i = 0; i < N; i++) {
	D[i] = (int )malloc(N sizeof(int));
	for (int j = 0; j < N; j++) {
	if (i == j)
	D[i][j] = 0;
	else
	D[i][j] = rand() % 100 + 1;
	}
	}

	for (int k = 0; k < N; k++) {
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	if (D[i][k] + D[k][j] < D[i][j]) {
	// P[i][j] = k + 1;
	D[i][j] = D[i][k] + D[k][j];
	}
	}
	}
	// cout << "k = " << (k + 1) << endl;
	}
	long end = clock();

	for (int i = 0; i < 5; i++) {
	for (int j = 0; j < 5; j++) {
	cout << setw(3) << D[i][j];
	}
	cout << endl;
	}

	cout << "\033[36mTotal: " << (end - start) / 1000.0 << " (sec)\033[0m"
	<< endl;

	free(D);
	return 0;
	}

# 平行版程式

	#include <bits/stdc++.h>
	#include <mpi.h>
	#define N 1000
	using namespace std;

	int main() {
	MPI_Init(NULL, NULL);
	int world_size, world_rank;
	MPI_Comm_size(MPI_COMM_WORLD, &world_size);
	MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);

	srand(36);

	double start = MPI_Wtime();
	int **D;
	D = (int *)malloc(N sizeof(int *));
	for (int i = 0; i < N; i++) {
	D[i] = (int )malloc(N sizeof(int));
	}

	if (world_rank == 0) {
	for (int k = 0; k < N; k++) {
	for (int j = 0; j < N; j++) {
	if (k == j)
	D[k][j] = 0;
	else
	D[k][j] = rand() % 100 + 1;
	}
	}

	for (int k = 0; k < N; k += world_size) {
	for (int i = 1; i < world_size; i++) {
	if (k + i < N) {
	MPI_Send(D[k + i], N, MPI_INT, i, k, MPI_COMM_WORLD);
	}
	}
	}
	} else {
	for (int k = 0; k < N; k += world_size) {
	if (k + world_rank < N) {
	MPI_Recv(D[k + world_rank], N, MPI_INT, 0, k, MPI_COMM_WORLD,
	MPI_STATUS_IGNORE);
	}
	}
	}

	for (int k = 0; k < N; k++) {
	MPI_Bcast(D[k], N, MPI_INT, k % world_size, MPI_COMM_WORLD);
	for (int i = 0; i < N; i += world_size) {
	for (int j = 0; j < N; j++) {
	if (i + world_rank < N) {
	D[i + world_rank][j] =
	min(D[i + world_rank][j], D[i + world_rank][k] + D[k][j]);
	}
	}
	}
	}

	if (world_rank == 0) {
	for (int k = 0; k < N; k += world_size) {
	for (int i = 1; i < world_size; i++) {
	if (k + i < N) {
	MPI_Recv(D[k + i], N, MPI_INT, i, k, MPI_COMM_WORLD,
	MPI_STATUS_IGNORE);
	}
	}
	}
	} else {
	for (int k = 0; k < N; k += world_size) {
	if (k + world_rank < N) {
	MPI_Send(D[k + world_rank], N, MPI_INT, 0, k, MPI_COMM_WORLD);
	}
	}
	}
	double end = MPI_Wtime();

	if (world_rank == 0) {
	for (int i = 0; i < 5; i++) {
	for (int j = 0; j < 5; j++) {
	cout << setw(3) << D[i][j];
	}
	cout << endl;
	}

	cout << "\033[36mTotal: " << (end - start) << " (sec)\033[0m" << endl;
	}

	free(D);
	MPI_Finalize();
	return 0;
	}