使用O(V + E)验证Dijkstra算法

Question

我正在解决这个问题:

Gaedel教授编写了一个程序，声称实现了Dijkstra算法。该程序为V中的每个顶点v生成v.d和v.π。请提供一种O.(V + E)时间复杂度的算法来检查教授程序的输出。它应确定d和π属性是否与某些最短路径树的属性匹配。您可以假设所有边权重均为非负数。

v.d是从起始节点到v的最短距离。 v.π是从起始节点到v的最短路径上的前驱节点

我的想法是： 对于每个顶点(i)，将i.d与(i.π).d进行比较。如果i的前驱节点具有更大的d值，则我们不能有最短路径树。

我相信这可以检查教授的输出是否不是最短路径树，但我认为没有更多信息的情况下无法确认输出是否为最短路径树。

我在正确的轨道上吗？

- user1754045

---

你打算用什么时间和工具来实现这个？运行SPA并查看它是否是树形结构。它已经被验证过是最好的了。 - ashley

我不确定SPA是什么。这个问题来自于《算法导论》第三版。我认为我只需要提供一个通用的算法，而不需要指定数据结构。我的解决方案运行时间为O(E+V)，因为我只访问每个顶点和边一次，但我不确定它是否正确。 - user1754045

最短路径算法。Dijkstra算法是最著名的算法之一。 - ashley

Dijkstra算法的时间复杂度为O(E + VlogV)，因此我不能使用它。它也可能产生一棵与教授所产生的最短路径树不相等的树。 - user1754045

Answer 1

我认为这个方法可以行得通。

进行深度优先搜索，但不是按照常规图边缘进行，而是只按照每个顶点的π值进行。您这样做是为了产生一个拓扑排序，以便第一个完成的顶点将是拓扑排序中的第一个顶点。请注意，您生成的拓扑排序中的第一个顶点将是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次。

- goat

---

是的，这似乎有效。使用顶部排序来查找最短路径图与我正在处理的几个部分相距甚远。这种方法将给出正确的起始顶点，并应该从教授创建的最短路径图中重新创建相同的图形。感谢您的帮助。 - user1754045