<分区>
我正在努力解决这个问题:
Gaedel 教授编写了一个程序，他声称该程序实现了 Dijkstra 算法。 该程序为 V 中的每个顶点 v 生成 v.d 和 v.π。给出一个 O.(V + E)-时间算法来检查教授程序的输出。它应该 确定 d 和 π 属性是否与某些最短路径树的属性相匹配。 您可以假设所有边权重都是非负的。
v.d 是起始节点到 v 的最短距离。 v.π是从起始节点到v的最短路径中v的前驱
我的想法是: 对于每个顶点 (i)，将 i.d 与 (i.π).d 进行比较。如果 i 的前任具有更大的 d 值，那么我们就不能拥有最短路径树。
我相信这可以检查教授的输出是否不是最短路径树，但我认为它不能确认输出是最短路径树。如果没有更多信息，我想不出一种方法来做到这一点。
我走在正确的轨道上吗？
最佳答案
我认为这可行
进行 DFS，但不是遵循常规图形边，而是仅遵循每个顶点的 π 值。您这样做是为了生成拓扑排序，以便第一个完成的顶点将是拓扑排序中的第一个顶点。请注意，您生成的拓扑排序中的第一个顶点将是提供给 Gaedel 算法的“源”顶点。
现在您有了拓扑排序，您可以以最有效的顺序松弛边，就像您在 DAG 上做的那样。
for each v in topoSortedVerts
if v.d_verify != v.d_Gaedel
//fail
for each u in v.adjacencies
relax(v, u)
if v.d_verify != v.d_Gaedel
//fail
我认为您可能还需要确保考虑了所有 V 顶点，并且源顶点匹配。或许。另外，我猜想 Gaedel 的由 π 值引起的前身子图可能是真正的被抬高了并且有各种疯狂的错误，但我认为它没有。
是O(V + E)因为外层循环运行了V次，内层循环使用了聚合分析运行了E次.
关于algorithm - 在 O(V + E) 中验证 Dijkstras 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13558800/