Floyd-Warshall algorithm

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] ;
}
}```