验证图形的最短路径

Question

[已编辑] 对于图 G，我们给出了从顶点 V1 到图的每个其他顶点的最短路径距离。我们如何验证给定的距离是人们可以找到的实际最短路径（通过 Dijkstra 或其他一些算法）？它的运行时间？

Answer 1

我假设你的图是有向的（无向的情况类似）。对于每条边 (u,v)，您必须验证 dist(v) <= dist(u) + length(u,v) 成立。此外，对于每个顶点 v，您需要一条边 (u,v)，使得 dist(v) = dist(u) + length(u,v)。这显然可以在 O(m) 时间内完成，这比仅应用另一个最短路径计算要快。此外，它不太可能有错误。