代码之家 › 专栏 › 技术社区 › P Shved

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

graph algorithm

P Shved · 技术社区 · 15 年前

关于地下爆炸的最新消息使我对以下问题感到好奇。假设我们有一个加权无向图,它的节点有时被移除。问题是在这样的删除之后快速地重新计算所有节点对之间的最短路径。

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

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

当图的节点被移除时,什么算法可以用来平衡所有对最短路径问题的查询和更新时间?

3 回复 | 直到 15 年前

Community CDub 8 年前

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

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

Unreason 15 年前

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

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

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

Ants Aasma 15 年前

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

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

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