71 lines
1.7 KiB
D
71 lines
1.7 KiB
D
import std.stdio;
|
|
|
|
void main() {
|
|
int[][] weights = [
|
|
[1, 3, -2],
|
|
[2, 1, 4],
|
|
[2, 3, 3],
|
|
[3, 4, 2],
|
|
[4, 2, -1]
|
|
];
|
|
int numVertices = 4;
|
|
|
|
floydWarshall(weights, numVertices);
|
|
}
|
|
|
|
void floydWarshall(int[][] weights, int numVertices) {
|
|
import std.array;
|
|
|
|
real[][] dist = uninitializedArray!(real[][])(numVertices, numVertices);
|
|
foreach(dim; dist) {
|
|
dim[] = real.infinity;
|
|
}
|
|
|
|
foreach (w; weights) {
|
|
dist[w[0]-1][w[1]-1] = w[2];
|
|
}
|
|
|
|
int[][] next = uninitializedArray!(int[][])(numVertices, numVertices);
|
|
for (int i=0; i<next.length; i++) {
|
|
for (int j=0; j<next.length; j++) {
|
|
if (i != j) {
|
|
next[i][j] = j+1;
|
|
}
|
|
}
|
|
}
|
|
|
|
for (int k=0; k<numVertices; k++) {
|
|
for (int i=0; i<numVertices; i++) {
|
|
for (int j=0; j<numVertices; j++) {
|
|
if (dist[i][j] > dist[i][k] + dist[k][j]) {
|
|
dist[i][j] = dist[i][k] + dist[k][j];
|
|
next[i][j] = next[i][k];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
printResult(dist, next);
|
|
}
|
|
|
|
void printResult(real[][] dist, int[][] next) {
|
|
import std.conv;
|
|
import std.format;
|
|
|
|
writeln("pair dist path");
|
|
for (int i=0; i<next.length; i++) {
|
|
for (int j=0; j<next.length; j++) {
|
|
if (i!=j) {
|
|
int u = i+1;
|
|
int v = j+1;
|
|
string path = format("%d -> %d %2d %s", u, v, cast(int) dist[i][j], u);
|
|
do {
|
|
u = next[u-1][v-1];
|
|
path ~= text(" -> ", u);
|
|
} while (u != v);
|
|
writeln(path);
|
|
}
|
|
}
|
|
}
|
|
}
|