algorithm - 如果节点被删除，如何在线重新计算所有对的最短路径？

Question

关于地下轰炸的最新消息让我对以下问题感到好奇。假设我们有一个加权无向图，有时会删除其中的节点。问题是在此类移除后快速重新计算所有节点对之间的最短路径。

对Floyd-Warshall algorithm进行简单修改我们可以计算所有对之间的最短路径。这些路径可能存储在一个表中，其中 shortest[i][j] 包含 i 和 j< 之间最短路径上的下一个节点的索引(如果没有路径，则为 NULL 值)。该算法需要 O(n³) 的时间来构建表，每个查询 shortest(i,j) 需要 O(1)。不幸的是，我们应该在每次删除后重新运行该算法。

另一种方法是对每个查询运行图形搜索。这样，每次删除更新辅助结构所需的时间为零(因为没有)，但每次查询都需要 O(E) 时间。

当删除图的节点时，可以使用什么算法来“平衡”所有对最短路径问题的查询和更新时间？

Answer 1

如 goran 所述，你只需要重新计算那些包含同时被删除的节点的最短路径。所以，我会执行以下操作:

1. 使用 Floyd-Warshall 算法计算所有最短路径。这是 O(n³)。
2. 创建一个索引，将顶点索引分配给顶点参与的最短路径列表。(换句话说，对于每个顶点 i，它会为您提供 (j, k) 对 s.t. i 存在于顶点 j 和 k 之间的最短路径中。这是 O(n²d)(其中 d 是图形直径)，因为您必须遍历每个最短路径中的每个顶点上一步确定的路径，有n²条这样的最短路径。
3. 顶点移除后，从第 2 步中创建的索引中查找受影响的最短路径列表并重新计算它们。由于您不需要此处的所有最短路径，并且我假设只有少数节点受到影响，因此您最好使用多个广度优先搜索，即 O(m + n ) 其中 m 是边的数量。