dynamic-dijkstra

Given a weighted directed graph, calculate shortest paths from a given point, supports a dynamically updating graph (including both adding and removing edges)

This is needed in secure scuttlebutt to calculate what portion of the network to replicate.

algorithm

The basic algorithm is just dijkstra's algorithm, and then there stuff to handle dynamic updates. Note that calculating shortest paths in a dynamically updating graph is a open problem, so no one knows what the best possible solution is. I have come up with some shortcuts that do sufficiently well for this to be used in secure-scuttlebutt. Unfortunately, I wasn't able to read most of the academic literature on this problem as it was too complicated for me.

dijkstra's algorithm

Given a graph g, and starting node S, set hops[S] = 0 and add S to a priority queue sorted in ascending order by hops value. While queue is not empty, take the first item in the queue, j and for each edge from j, j->k with weight v, check if hops[k] is undefined or higher than hops[j] + v if so, set hops[k] = hops[j] + v and add k to the priority queue and continue.

Note: all edges must be positive. In secure-scuttlebutt we use negative edges to represent various kinds of edge removal, such as unfollow and block. These are handled specially, see api documentation below.

adding edges

Adding edges is easy, adding an edge can either cause no change in the path lengths, or decrease them. If the adding an edge from j->k (with weight v) does not change the distance to k, then we are already done. That is, if hops[k] == hops[j] + v. If adding an edge does reduce the shortest path to k, it may also reduce the length of paths from k, so set the new value of hops[k], and run dijkstra's algorithm starting from k.

removing edges

Removing edges is a lot more complicated. Here the shortest paths may become longer. The naive implementation is to just to rerun dijkstra's algorithm from scratch, but this is very expensive if a lot of edges are removed. We calculate a conservative set of nodes which may become longer with the removal of the edge j->k. This set is calculated by starting with k, and finding all nodes reachable from k, that currently have a shortest path distance greater than k. note: in this traversable, "reachable" means that for an edge a->b, with weight w, hops[b] == hops[a] + w if hops[b] > hops[a] + w that means the shortest path to b is not through b, so we won't update the distance to b because of this edge.

Note, in our usecase of secure scuttlebutt, most weights are whole numbers, so often there are many paths which are equally short, if you used this module on a graph with a different distribution of edge weights, performance may differ significantly.

Once we have the set of maybe nodes, we get the set of sources, the set of all nodes from which the shortest paths into those nodes may come from. These are the nodes which have edges into the maybe set. To calculate this efficiently, we maintain a data structure of the graph with edges reversed. for each node in the maybe set, m we check all edges s->m with weight w, and if hops[s] + w == hops[m] then we add s, other edges can be ignored.

Then, we delete the current hops values for every node in the maybe set, and rerun dijkstra's algorithm from every node in the source set.

api: DynamicDijkstra(options: Options) => traverser

for given configuration options, initialize a new traverser object. the options defines the meaning various operations used in the algorithm.

traverser.traverse(g, _g, max, start) => hops

traverse g starting from start and return the shortest path length to all nodes reachable from start with path length less than max.

_g is the reverse of g. such that g[j][k] = _g[k][j]

traverser.update (g, _g, hops, max, start, from, to, value) => diff

add an edge from->to with weight value to g and _g, and update hops to reflect any changes in the shortest path. hops must be the correct shortest paths from start on the graph prior to adding the edge from->to, value.

returns shortest path lengths that changed, and {[k]: null,..} if a node k now no longer has a shortest path less than max.

Options: {min, add, initial, expand, isAdd}

the options object defines the operations needed to process the traversal. in secure-scuttlebutt these are just floats,

min (a, b)

min returns the lower of two arguments. the return value must be the same with either argument order: min(a, b) === min(b, a)

add (a, v)

Add an edge value to a path length. hop lengths must always get longer. so the min of any possible edge value added to any length must always be greater than that length. min(a, add(a, v)) == a (the min must be the original length)

isAdd(v)

return true if this value represents an edge addition.

expand (length, max)

return true if length is considered less than max, or otherwise paths may extend from it.

License

MIT