有关地下爆炸的最新消息让我对以下问题感到好奇。假设我们有一个带权的无向图，其中的节点有时会被删除。问题是在清除这些删除之后快速重新计算所有节点对之间的最短路径。如何在线删除节点时重新计算所有对最短路径？
通过对Floyd-Warshall algorithm的简单修改，我们可以计算所有配对之间的最短路径。这些路径可能存储在一个表中，其中shortest[i][j]包含i和j（或NULL值，如果没有路径）之间最短路径上的下一个节点的索引。该算法需要O（n³）时间来建立表格，并且每个查询shortest(i,j)需要O（1）。不幸的是，我们应该在每次移除后重新运行此算法。
另一种选择是在每个查询上运行图搜索。这样每次移除都需要零时间来更新辅助结构（因为没有），但每个查询都需要O（E）时间。
当图的节点被删除时，什么算法可以用来“平衡”所有对最短路径问题的查询和更新时间？
嗯，我不认为你需要重新运行整个构建，如果一个节点被删除。只适用于那些有节点的路径。
问题的一般解决方案是添加有关冗余路径的信息，例如对于最短路径上的每个节点可以有第二个最短路径。 这不会减少计算时间，但会缓存它（它也会将存储需求增加n倍，其中n是平均节点数，对于单个节点删除，按n *（n-1）2节点冗余...和因子n！用于完全冗余，并且还以相同因子增加初始建立时间，并且还增加了添加节点所需的时间）
如果有一种方法可以改善这种情况并减少重建那么你需要找到一个能够快速计算最短距离的结构，但是当节点被删除或添加到图形时，这应该是不可变的（或者重新计算便宜）。
如goran所述，您只需重新计算那些包含在此期间被删除的节点的最短路径。因此，我会执行以下操作：
我会回答问题的隐含非通用变体，其中图形是道路网络。在我看来，任意图的理论界限不那么有趣的情况之一。
最短路径查找的一些最佳方法是公路节点路由和传输节点路由。 （在dissertation by Dominik Schultes中描述）。加速结构可以合理快速地建立（对于整个欧洲的HNR约为15分钟）并且它支持增量更新。有趣的是，随机查询的查询时间大约为1ms，并且每对条目的距离表可以低至0.2us计算。更有趣的是查询性能缩放，数据表明缩放在图形大小上是次对数/近似不变的。在4.3us随机查询中，Transit节点路由更快。唉，我没有关于数据结构可更新性的任何信息。直观地说，增量更新应该不会太难。
相同或相似的方法可以用于其他与道路网络相似的图形（稀疏，平面，分层）。