如何在 O(n log n + m) 时间内使用 d 和 π 数组检查 G 中从 s 到 t 的最短路径是否唯一？
How to use the d and π array to check if the shortest path from s to t in G is unique or not, in O(n log n + m) time?
给定一个有向图G = (V, E)，权重函数为正：w : E → R>0，有两个顶点s, t ∈ V。假设我们已经使用 Dijkastra 算法计算了 d 和 π 数组：d[v] 是从 s 到 v 的最短路径的长度，π[v] 是路径中 v 之前的顶点。
我们如何使用 d 和 π 数组来检查从 s 到 t 的最短路径是否在
G是否唯一，在O(n log n + m)时间内？
对于沿着最短路径的每条边 (u->v)，考虑我们可以到达 v 的所有其他方式——也就是说，考虑存在边 (x->v) 的所有其他顶点 x。如果 shortest_path(s to u)+|u->v| 与 shortest_path(s to x)+|x->v| 的长度相同（其中 |u->v| 表示该边的长度），那么从 s 到 t 的最短路径不止一条。
我认为这个 if 语句很容易理解，但如果不是，请告诉我。我们还应该检查如果最短路径是非唯一的，那么这个过程总能找到它。直觉上，我认为这是真的，如果它是真的，你可能可以通过假设存在一条不同于 π 中描述的最短路径来证明它，这意味着第二最短路径至少在某些方面偏离 π地方，并探索其逻辑结论。
给定一个有向图G = (V, E)，权重函数为正：w : E → R>0，有两个顶点s, t ∈ V。假设我们已经使用 Dijkastra 算法计算了 d 和 π 数组：d[v] 是从 s 到 v 的最短路径的长度，π[v] 是路径中 v 之前的顶点。
我们如何使用 d 和 π 数组来检查从 s 到 t 的最短路径是否在 G是否唯一，在O(n log n + m)时间内？
对于沿着最短路径的每条边 (u->v)，考虑我们可以到达 v 的所有其他方式——也就是说，考虑存在边 (x->v) 的所有其他顶点 x。如果 shortest_path(s to u)+|u->v| 与 shortest_path(s to x)+|x->v| 的长度相同（其中 |u->v| 表示该边的长度），那么从 s 到 t 的最短路径不止一条。
我认为这个 if 语句很容易理解，但如果不是，请告诉我。我们还应该检查如果最短路径是非唯一的，那么这个过程总能找到它。直觉上，我认为这是真的，如果它是真的，你可能可以通过假设存在一条不同于 π 中描述的最短路径来证明它，这意味着第二最短路径至少在某些方面偏离 π地方，并探索其逻辑结论。