Spaces:
Build error
Build error
File size: 1,266 Bytes
c211499 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
import * as _ from 'lodash-es';
export { floydWarshall };
var DEFAULT_WEIGHT_FUNC = _.constant(1);
function floydWarshall(g, weightFn, edgeFn) {
return runFloydWarshall(
g,
weightFn || DEFAULT_WEIGHT_FUNC,
edgeFn ||
function (v) {
return g.outEdges(v);
}
);
}
function runFloydWarshall(g, weightFn, edgeFn) {
var results = {};
var nodes = g.nodes();
nodes.forEach(function (v) {
results[v] = {};
results[v][v] = { distance: 0 };
nodes.forEach(function (w) {
if (v !== w) {
results[v][w] = { distance: Number.POSITIVE_INFINITY };
}
});
edgeFn(v).forEach(function (edge) {
var w = edge.v === v ? edge.w : edge.v;
var d = weightFn(edge);
results[v][w] = { distance: d, predecessor: v };
});
});
nodes.forEach(function (k) {
var rowK = results[k];
nodes.forEach(function (i) {
var rowI = results[i];
nodes.forEach(function (j) {
var ik = rowI[k];
var kj = rowK[j];
var ij = rowI[j];
var altDistance = ik.distance + kj.distance;
if (altDistance < ij.distance) {
ij.distance = altDistance;
ij.predecessor = kj.predecessor;
}
});
});
});
return results;
}
|