动态更新最短路径

Question

我有一个图表，经常需要知道所有最短路径（或者它们的长度）。因为我不想重新计算它们，所以我将它们存储在一个简单的数组中，并从那里检索它们。然而，由于图表可能随着时间的推移而发生变化，因此我将不得不在特定时间重新计算它们。

目前可能发生以下更改：

- 向图表添加节点和边 - 更改边的长度 - 向图表添加新边 - 删除边或删除节点

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

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

编辑：正如一些人指出的那样，当添加节点或更改链接时，可能需要重新计算所有内容。例如，如果所有距离都通过更新更改，则可能需要重新计算。但是，如果我只是通过图形传播更改并执行类似于Dijkstra的松弛，那么我可能必须多次松弛相同的节点，因为我可能不选择最佳顺序。问题在于如何排序松弛步骤，以尽可能避免多次更新。

不确定没有实际想法是否有多大意义，但我希望这可以更清楚一些。

- LiKao

---

你有一个根节点和从它出发的所有最短路径，还是所有节点之间的最短路径？ - Yochai Timmer

不，没有根节点，而是所有最短路径长度的对。 - LiKao

每当有两个点可以通过修改连接路径时，您都需要重新计算最短路径。 - Ricky Bobby

Answer 1

D*算法家族专注于在动态变化的图中更新最短路径。该算法是为移动机器人路径规划问题而开发的。虽然该算法仅返回从目标到当前机器人位置的最短路径，但您可能也可以使用它们的记账和更新规则来解决所有最短路径问题。

- antonakos

Answer 2

当你删除一个边/节点时，你可以很容易地处理这种情况。只需跟踪节点之间的实际路径。然后，当删除一个边/节点时，遍历路径并查看哪些路径受到更改的影响。重新计算这些路径的最短路径。

在增加边权重的情况下，您可以使用相同的技术。

其他情况要处理起来就困难得多。我不知道有任何算法/数据结构可以加速重新计算。

- tskuzzy

---

告诉我如果我错了，但在你的第一个情况中，你将不得不跟踪所有可能的路径，而不仅仅是最短路径。并且对于每一对节点都要这样做，那是需要跟踪的很多东西。 - Ricky Bobby

为什么需要所有可能的路径？删除边/节点只会使最短路径变得更长。我们只需要查看最短路径是否已更改（即是否已删除路径上的某些内容）。 - tskuzzy

我在考虑一个完全图，所以在我的脑海中，删除后最短路径总是会增加。在这种情况下，您只需计算每对节点的新路径即可。 - Ricky Bobby

我不确定在删除后会发生什么（例如，只是删除与此节点链接的所有边缘？）...但我有一种感觉，它可能会影响非最优路径以及最优路径。因此，最优路径的成本可能会降低，而次优路径的成本可能会降低更多。无论如何，我认为对于这个普遍问题没有简单的解决方案，即使您的解决方案看起来很有吸引力。在大多数情况下，您将不得不重新计算路径。 - Ricky Bobby

如果最优路径不包括被删除的节点，则它不会受到影响。但是，如果包括该节点，则你是正确的，最优路径可能会改变。这就是为什么你必须再次运行最短路径算法的原因。 - tskuzzy