algorithm - 寻找通过特定顶点之间的最短路径

Question

我有这个问题给定一个具有正边权重和地标顶点 x 的有向图 G，您的目标是找到从一个顶点 v 到另一个顶点 w 并通过地标 x 的最短路径的长度。

需要为该问题描述一个 O(E log V ) 算法。我知道 Dijkstra 算法的复杂度是 O(ElogV)。

请你帮我解决这个问题。

Answer 1

如果您首先使用 Dijkstra 算法找到从 v 到 x，p_1 和从 x 到 w，p_2 的最短路径，并将这些路径 p 串联起来，那么这将是从 v 到 w 通过 x 的最短路径。

如果有一条更短的路径 p'，那么在 x 处拆分这条路径会产生一条从 v 到 x 的路径 p_1' 和一条从 x 到 w 的路径 p_2'，其中 p_1' 比 p_1 或 p_2' 短比 p_2 短(否则 length(p_1'+p_2') > length(p_1+p_2))这是矛盾的。

编辑:这显然是 O(E logV)，因为它只使用了 Dijkstra 两次。