G 是仅具有正权重的连通无向图。 S是最短路径树(不一定是G的SPT)。所以我要设计一个算法来检查图S是否是图G的最短路径树。
我的算法是……
在 G 和 S 上运行 Dijkstra 算法(返回图，而不是最短路径)。检查每个顶点的 dist(v) 值，如果都相同，则 S 是 G 的最短路径树。
我不知道这个算法行不行，但我觉得是合理的。如果是真的我如何证明它的正确性，如果不是，一个反例会很有帮助吗？
* 我也在 CS Exchange 上发布了这个 *
最佳答案
反证法:
假设 S 是 G 的最短路径树(具有相同的根)，并且存在一个顶点 v，其中 Dijkstra 算法的 dist(v) 不等于它在 S 中的距离。
让我们检查这两个选项:
Dijkstra 算法在 G 上的 dist(v) 大于它在 S 中的值。如果是这样，这意味着 Dijkstra 算法是错误的，因为到该顶点的路径更短。
<Dijkstra 算法在 G 上的 dist(v) 小于它在 S 中的值 - 这意味着 S 不能是有效的最短路径树，因为存在到顶点 v 的更短路径，因此与我们的初始值相矛盾假设。
Q.E.D.
关于algorithm - 检查图 S 是 G 中的最短路径树(算法 + 正确性)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21986706/