检查图 S 是 G 中的最短路径树(算法 + 正确性)

Question

G 是一个仅具有正权重的连接无向图。S 是最短路径树（不一定是 G 的 SPT）。所以我要设计一个算法来检查图S是否是图G的最短路径树。

我的算法是这样的。

在 G 和 S 上运行 Dijkstra 算法（返回图形，而不是最短路径）.检查每个顶点的 dist（v） 值，如果都相同，则 S 是 G 的最短路径树。

我不知道这个算法是否有效，但我认为它是合理的。如果它是真的，我如何证明它的正确性，如果不是，反例会很有帮助？

*

我也在 CS Exchange 上发布了这个 *

Answer 1

矛盾证明：

假设 S 是 G 的最短路径树（具有相同的根），并且存在一个顶点 v，其中来自 Dijkstra 算法的 dist（v） 不等于它在 S 中的距离。

让我们检查一下这两个选项：

1. Dijkstra 算法在 G 上的 dist（v） 大于它在 S 中的值。如果是这样，这意味着Dijkstra的算法是错误的，因为到这个顶点的路径更短。

2. Dijkstra 算法在 G 上的 dist（v） 小于它在 S 中的值 - 这意味着 S 不可能是有效的最短路径树，因为存在指向顶点 v 的较短路径，因此与我们最初的假设相矛盾。

质检部