Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | 16x 7x 12x 7x 7x 7x 19x 19x 19x 19x 61x 42x 19x 19x 19x 19x 7x 19x 19x 19x 61x 61x 61x 211x 211x 211x 211x 211x 211x 12x 12x 7x | import Graph, { DefaultEdgeType } from '../Graph';
const DEFAULT_WEIGHT_FUNC = () => 1;
export function floydWarshall<NodeIDType, EdgeType>(
graph: Graph<NodeIDType, any, EdgeType>,
weightFn?: (node: DefaultEdgeType<NodeIDType, EdgeType>) => number,
edgeFn?: (node: NodeIDType) => DefaultEdgeType<NodeIDType, EdgeType>[],
) {
return runFloydWarshall(
graph,
weightFn || DEFAULT_WEIGHT_FUNC,
edgeFn ||
function (v: NodeIDType) {
return graph.outEdges(v)!;
},
);
}
type Entry<NodeIDType> = {
distance?: number;
predecessor?: NodeIDType;
};
function runFloydWarshall<NodeIDType, EdgeType>(
graph: Graph<NodeIDType, any, EdgeType>,
weightFn: (node: DefaultEdgeType<NodeIDType, EdgeType>) => number,
edgeFn: (node: NodeIDType) => DefaultEdgeType<NodeIDType, EdgeType>[],
) {
var results: Record<string, Record<string, Entry<NodeIDType>>> = {};
var nodes = graph.nodes();
nodes.forEach(function (node) {
const v = String(node);
results[v] = {};
results[v][v] = { distance: 0 };
nodes.forEach(function (w) {
if (node !== w) {
results[v][String(w)] = { distance: Number.POSITIVE_INFINITY };
}
});
edgeFn(node).forEach(function (edge) {
const w = edge.v === node ? edge.w : edge.v;
let d = weightFn(edge);
results[v][String(w)] = { distance: d, predecessor: node };
});
});
nodes.forEach(function (nodek) {
const k = String(nodek);
var rowK = results[k];
nodes.forEach(function (nodei) {
const i = String(nodei);
var rowI = results[i];
nodes.forEach(function (nodej) {
const j = String(nodej);
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;
}
export default floydWarshall;
|