51 lines
1.2 KiB
JavaScript
51 lines
1.2 KiB
JavaScript
var _ = require('../lodash')
|
|
|
|
module.exports = 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) {
|
|
const results = {}
|
|
const 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) {
|
|
const w = edge.v === v ? edge.w : edge.v
|
|
const 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
|
|
}
|