66 lines
2.3 KiB
C#
66 lines
2.3 KiB
C#
using System;
|
|
|
|
namespace FloydWarshallAlgorithm {
|
|
class Program {
|
|
static void FloydWarshall(int[,] weights, int numVerticies) {
|
|
double[,] dist = new double[numVerticies, numVerticies];
|
|
for (int i = 0; i < numVerticies; i++) {
|
|
for (int j = 0; j < numVerticies; j++) {
|
|
dist[i, j] = double.PositiveInfinity;
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < weights.GetLength(0); i++) {
|
|
dist[weights[i, 0] - 1, weights[i, 1] - 1] = weights[i, 2];
|
|
}
|
|
|
|
int[,] next = new int[numVerticies, numVerticies];
|
|
for (int i = 0; i < numVerticies; i++) {
|
|
for (int j = 0; j < numVerticies; j++) {
|
|
if (i != j) {
|
|
next[i, j] = j + 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
for (int k = 0; k < numVerticies; k++) {
|
|
for (int i = 0; i < numVerticies; i++) {
|
|
for (int j = 0; j < numVerticies; j++) {
|
|
if (dist[i, k] + dist[k, j] < dist[i, j]) {
|
|
dist[i, j] = dist[i, k] + dist[k, j];
|
|
next[i, j] = next[i, k];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
PrintResult(dist, next);
|
|
}
|
|
|
|
static void PrintResult(double[,] dist, int[,] next) {
|
|
Console.WriteLine("pair dist path");
|
|
for (int i = 0; i < next.GetLength(0); i++) {
|
|
for (int j = 0; j < next.GetLength(1); j++) {
|
|
if (i != j) {
|
|
int u = i + 1;
|
|
int v = j + 1;
|
|
string path = string.Format("{0} -> {1} {2,2:G} {3}", u, v, dist[i, j], u);
|
|
do {
|
|
u = next[u - 1, v - 1];
|
|
path += " -> " + u;
|
|
} while (u != v);
|
|
Console.WriteLine(path);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
static void Main(string[] args) {
|
|
int[,] weights = { { 1, 3, -2 }, { 2, 1, 4 }, { 2, 3, 3 }, { 3, 4, 2 }, { 4, 2, -1 } };
|
|
int numVerticies = 4;
|
|
|
|
FloydWarshall(weights, numVerticies);
|
|
}
|
|
}
|
|
}
|