3

我正在努力解决这个问题：

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

vd 是从起始节点到 vvπ 的最短距离是 v 在从起始节点到 v 的最短路径中的前任

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

我相信这可以检查教授的输出是否不是最短路径树，但我认为它不能确认输出是最短路径树。如果没有更多信息，我想不出办法做到这一点。

我在正确的轨道上吗？

4

1 回答 1

3

我认为这会奏效

做一个 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使用聚合分析运行时间。

于 2012-11-26T06:06:05.877 回答