algorithm - 在更新图形时保持最短路径

Question

我想知道所有对之间的距离(例如 dijkstra。具体来说，我正在使用 networkx)然后，当将边添加到图形时，我想更新距离而无需从头开始重新计算。

如何做到这一点？谢谢

Answer 1

无需重新计算所有最短路径是可能的，但成本仍然很高 O(n^2) .

因此，假设您有一个距离矩阵 M大小为 n*n，其中每个条目 M_{i,j}包含距节点 i 的距离到节点 j .假定 M 是由某种算法预先计算的。

现在如果有一条新边e_{i,j}被添加到节点 i 之间的图中和节点 j成本w_{i,j} ，你检查是否w_{i,j} < M_{i,j} .如果不是，则无需更改任何内容。但如果它成立，那么图中的最短路径可能会有所改善。

然后对于每个节点对k, l您检查通过新边的路径是否比先前计算的路径短。这可以通过评估以下内容来完成。

M_{k,l} > min (M_{k,i} + w_{i,j} + M_{j,l} , M_{k,j} + w_{j,i} + M_{i,l})

如果这成立，那么您可以替换 M_{k,l}通过 min (M_{k,i} + w_{i,j} + M_{j,l} , M_{k,j} + w_{j,i} + M_{i,l})

以上适用于单向图，但也适用于双向图。

编辑 1

我坚信\Omega(n^2) 也是这个问题的下界。假设您有两个断开连接的图形区域，都包含 n/2 个顶点。然后，如果您添加一条连接这些区域的新边，您将不得不更新 n/2 * n/2 条最短路径，导致至少 O(n^2) 运行时间。

编辑2

第二个想法是尝试利用上述等式，但首先遍历图形以找到必须首先更新的所有顶点对。思路示意图如下:

从节点 i 开始一个 Dijkstra。每当你到达顶点 k 时，你检查是否 M_{k, i} + w_{i, j} < M_{k, j}如果是，则将 k 添加到必须更新的顶点集 U 中。如果不是，那么您可以停止探索 k 之后的更多路径，因为“超出”k 的顶点不会使用 e_{i, j} 作为最短路径。

然后对节点 j 做同样的事情。然后按照上述思路对U中的所有顶点对进行M的更新。