如何利用d和π数组在O(n log n + m)时间内检查G中从s到t的最短路径是否唯一？

Question

我们给定一个有向图G=（V，E），权重函数为正：w : E → R>0，两个顶点s，t∈V 。假设我们已经用Dijkastra的算法计算出d和π数组：d[v]是s到v的最短路径的长度，π[v]是路径中v之前的顶点。

我们如何利用d和π数组在O(n log n + m)时间内检查G中从s到t的最短路径是否唯一？

Answer 1

对于沿着最短路径的每一条边(u->v)，考虑我们可以到达v的所有其他方式--也就是说，考虑所有其他顶点x，那里有一条边(x->v)。 如果 shortest_path(s to u)+|u->v| 是相同的长度 shortest_path(s to x)+|x->v| (其中 |u->v| 表示该边的长度）那么从s到t的最短路径不止一条。

我认为这个if-statement很容易理解，但如果不容易理解，请告诉我。 我们还应该检查一下，如果最短路径是非唯一的，那么这个过程总会发现这一点。 直觉上，我认为这是真的，如果是真的，你大概可以通过假设存在一个除π描述的最短路径之外的其他最短路径来证明它，说明这意味着第二个最短路径至少在某些地方偏离了π，并探讨其中的逻辑结论。

Answer 2

这是shi利的HW-5的一部分。请不要作弊。我看到你的另一条留言，说用MOSS做DS赋值。