On Saturday, 21 September 2013 at 15:49:00 UTC, rasmus svensson
wrote:
Assuming the shortest path from from all nodes to every other
node is already pre-computed:
What is a fast algorithm to update all paths, if one node is
marked as inpassible.
Any good 3rd party library or research paper out there?
A short note on worst case complexity. In a star graph, if you
remove the central vertex, *all* paths between pairs of other
vertices are affected (they become pairwise unreachable). So, if
there is a way to do it in less than V^2, it will at least have
to store paths in some sophisticated way, better than just a VxV
matrix with one element for each path.
Ivan Kazmenko.
