我有一个曲线图上，我经常需要了解的所有最短路径（或者更确切地说，它们的长度）。因为我不想重新计算他​​们，我将它们存储在一个简单的数组，并从那里只是检索它们。然而，由于该图也可能随时间而改变，我将不得不重新计算，在给定的时间。

I have a graph on which I frequently need to know all shortest paths (or rather their lengths). Because I do not want to recalculate them I store them in a simple array and just retrieve them from there. However since the graph might also change over time I will have to recalculate them at given times.

对于现在的以下变化可能会发生：

For now the following changes might happen:

添加节点和边缘给它的图

Adding a node and an edge to it to the graph

改变一个边缘的长度

添加图形的一个新的边缘

Adding a new edge of the graph

删除边缘或删除一个节点

Deleting an edge or deleting a node

在所有情况下的所有节点都将一直连接和所有边缘都积极的权重。还是无向图。操作序列是这样的，即所有节点将总是从图中的同样的部件。如果一个节点或边缘此其它节点和边之前被删除将已被添加，使得图形从未变得分离。

In all cases all nodes will always be connected and all edges have positive weights. Also the graph is undirected. The sequence of operations is such, that all nodes will always be from the same component of the graph. If a node or edge is deleted before this other nodes and edges will have been added so that the graph never becomes separated.

现在我打算只是做了更新，然后通过传播该图结构中的所有变化。但是我还没有确定如何正确处理这个问题。你将如何努力实现缓存长度的这些更新。

For now I am planning to just do the updates and then propagate all the changes through the graph structure. However I am not sure yet how to handle this correctly. How would you try to achieve these updates of the cached length.

修改

由于你们有些人指出这可能是neccessary重新计算一切，当一个节点添加或链接改变。这可能是例如当所有的距离通过更新变化。但是，如果我只是传播通过图中的变化，做同样的，这样做是dijk​​stras的方式放松，我可能会放松同一节点多次，因为我可能不会选择最优次序。现在的问题是如何订购舒张步骤，所以我尽量避免多次更新尽可能的好。

As some of you have pointed out it might be neccessary to recalculate everything when a node is added or a link is changed. This might be for example when all distances change through the update. However if I just propagate the changes through the graph and do a relaxation similar to the way it is done dijkstras, I might have to relax the same node multiple times, because I might not choose the optimal order. The question would be how to order the relaxation steps, so I avoid multiple updates as good as possible.

不知道这使多大意义，没有实际的想法我有想法，但我希望这澄清了一些。

Not sure this makes much sense without the actual idea I have in mind, but I hope this clarifies some more.

推荐答案

在 D *系列搜索算法的被精确涉及短路在动态变化的图表路径的更新。该算法是机器人路径规划问题的发展。虽然算法只返回从目标到当前机器人位置的最短路径，则可能能够使用自己的簿记和更新的规则进行全最短路径问题了。

The D* family of search algorithms are exactly concerned with the updating of shorting paths in dynamically changing graphs. The algorithms were developed for mobile robot path planning problems. Although the algorithms only return the shortest path from the goal to the current robot location, you might be able to use their bookkeeping and updating rules for all-shortest-paths problems too.