如果要删除节点,如何在线重新计算所有最短路径对?

如所述 goran ,只需重新计算包含同时删除的节点的最短路径。因此,我将执行以下操作:

1. 使用Floyd-Warshall算法计算所有最短路径。这是O( n个 ^三 ).
2. 创建一个索引,将顶点索引指定给顶点参与的最短路径列表。(换句话说,对于每个顶点 我 ,它会给你一个列表 (j,k) 成对s.t。 我 存在于顶点之间的最短路径中 j型 和 千 ). 这是O( n个 ^2个 丁 )(其中 丁 是图形直径),因为必须在上一步中确定的每个最短路径中的每个顶点上循环,并且 n个 ^2个 这么短的路。
3. 顶点删除后,从步骤2中创建的索引中查找受影响的最短路径列表并重新计算它们。因为这里不需要所有的最短路径,而且我假设只有几个节点受到影响,所以最好使用多个广度优先搜索,即( 米 + n个 )其中 米 是边的数目。

好吧,我不认为你需要重新运行整个构建如果一个节点被删除。只适用于那些有节点的路径。

解决问题的简单方法是添加有关冗余路径的信息,例如,对于最短路径上的每个节点,都可以有第二条最短路径。 这不会减少计算时间,但会将其缓存(它还会将存储需求增加一倍n,其中n是平均节点数,对于单节点删除,对于2节点冗余,它会增加一倍n*(n-1)。。。加上n!对于完全冗余,也会以相同的因子增加初始构建时间,同时也会增加添加节点所需的时间)

如果有一种方法可以改进这一点并减少重建时间,那么您需要找到一种结构,该结构允许快速计算最短距离,但在删除节点或将节点添加到图中时,该结构应该是不可变的(或重新计算成本较低)。

我将回答这个问题隐含的非泛型变体,其中的图形是一个道路网络。在我看来,这是任意图的理论界不那么有趣的情况之一。

寻找最短路径的一些最佳方法是公路节点路由和过境节点路由。(描述于 dissertation by Dominik Schultes ). 加速结构可以相当快地构建(整个欧洲的HNR大约15分钟),并且支持增量更新。有趣的是,随机查询的查询时间大约为1ms,所有成对的距离表可以计算为每个条目0.2us。更有趣的是查询性能的缩放,数据显示缩放在图形大小上是次对数/接近常数。传输节点路由在4.3us随机查询时更快。唉,我没有任何关于数据结构可更新性的信息。直观地说,增量更新应该不会太难。

相同或相似的方法可用于类似于道路网络(稀疏、平面、层次)的其他图形。