algorithm - 使用 dijkstra 从队列中弹出最短路径的节点

Question

我有一条使用正确实现的 dijkstra 算法计算出的最短路径。它从 A 经 B、C、D 和 E 到达 F。所以整个最短路径是 [A, B, C, D, E, F]。

现在我想从 G 到 F。当从队列中弹出 C 时，我意识到它是到 F 的最短路径的一部分。这是否意味着我也知道从 G 到 F 的最短路径是 [G , H, C, D, E, F]?

Answer 1

没有。但它确实意味着从C到F的最短路径是[C, D, E, F]。

如果有更短的路径 P 那么我们构造一条从 A 到 F [A,B,[P]] 的新路径，它本质上比我们原来的路径更短。这是一个矛盾，因为我们假设 [A,B,C,D,E,F] 是从 A 到 F 的最短路径。

这可以推广证明最短路径的子路径也是最短路径。在您的情况下，这意味着如果从 G 到 F 的最短路径包含 C，则该最短路径包含 [C, D, E, F] 作为子路径。由于您不知道 C 是否在您的最短路径中，如果您存储从 C 到 F 的最短路径的权重，则该定理只会帮助您减少计算次数。