algorithm - 动态更新最短路径

Question

我有一个图表，我经常需要在上面知道所有最短路径(或者更确切地说是它们的长度)。因为我不想重新计算它们，所以我将它们存储在一个简单的数组中，然后从那里检索它们。然而，由于图表也可能随时间变化，我将不得不在给定时间重新计算它们。

目前可能会发生以下变化:

• 向图中添加一个节点和一条边

• 改变边的长度

• 添加图的新边

• 删除边或删除节点

在所有情况下，所有节点都将始终连接并且所有边都具有正权重。该图也是无向的。操作顺序是这样的，所有节点将始终来自图形的同一组件。如果在添加其他节点和边之前删除了一个节点或边，则该图永远不会分离。

现在我计划只进行更新，然后通过图形结构传播所有更改。但是我还不确定如何正确处理这个问题。您将如何尝试实现缓存长度的这些更新。

编辑:

正如你们中的一些人指出的那样，当添加节点或更改链接时可能需要重新计算所有内容。这可能是例如当所有距离通过更新改变时。但是，如果我只是通过图表传播更改并进行类似于 dijkstras 的松弛，我可能不得不多次松弛同一个节点，因为我可能不会选择最佳顺序。问题是如何对松弛步骤进行排序，因此我尽可能避免多次更新。

如果没有我脑海中的实际想法，我不确定这是否有意义，但我希望这能澄清更多。

Answer 1

D* family of search algorithms正是关注动态变化图中短路路径的更新。这些算法是针对移动机器人路径规划问题开发的。尽管这些算法仅返回从目标到当前机器人位置的最短路径，但您也可以使用它们的簿记和更新规则来解决所有最短路径问题。