Floyd-Warshall algorithm

 avatar
user_3763047219
c_cpp
2 years ago
1.5 kB
1
Indexable
Never
#include <iostream>

int main()
{
	int n = 0, m = 0;
	static int E[201][2] = {};
	static float w[201][3] = {};
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %f %f", &E[i][0], &E[i][1], &w[i][0], &w[i][1]);
	}
	for (int i = 1; i <= m; i++) {//m
		if (w[i][0] > w[i][1]) {
			w[i][2] = w[i][0] - w[i][1];
		}
		else {
			w[i][2] = w[i][1] - w[i][0];
		}
	}
	static float c[51][51] = {};//造一個點對點的矩陣
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) {
				c[i][j] = 0;
			}
			else {
				c[i][j] = 999999;
			}
		}
	}
	for (int i = 1; i <= m; i++) {//把已有的權重放進矩陣
		c[E[i][0]][E[i][1]] = w[i][2];
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i != j) {//相等不用做
					if (c[i][j] > c[i][k] + c[k][j]) {
						c[i][j] = c[i][k] + c[k][j];
					}
				}
			}
		}
	}

	for (int i = 1; i < n; i++) {
		for (int j = 1; j < n; j++) {
			if (c[i][j] == 999999) {
				std::cout << "N" << " ";
			}
			else {
				std::cout << c[i][j] << " ";
			}
		}
		if (c[i][n] == 999999) {
			std::cout << "N" ;
		}
		else {
			std::cout << c[i][n] ;
		}
		std::cout << "\n";
	}

	for (int j = 1; j < n; j++) {
		if (c[n][j] == 999999) {
			std::cout << "N" << " ";
		}
		else {
			std::cout << c[n][j] << " ";
		}
	}
	if (c[n][n] == 999999) {
		std::cout << "N" ;
	}
	else {
		std::cout << c[n][n] ;
	}
}