确认为O Dijkstras算法（V + E）

我正在解决这个问题：确认为O Dijkstras算法（V + E）

Gaedel教授撰文指出，他声称一个程序实现Dijkstra算法。该程序为V中的每个顶点v生成v.d和v.π。给出一个 O（V + E）时间算法来检查教授程序的输出。应该由确定d和π属性是否匹配某些最短路径树的属性。你可以假定所有的边权重都是非负的。

VD是从起始节点到v的最短距离 v.π为v在最短路径前身从起始节点到v

我的想法是：对于每一个顶点（I），比较用的ID （i.π）.D。如果我的前任有更大的d值，那么我们不能有最短路径的树。

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

我在正确的轨道上吗？

来源

2012-11-26 user1754045

在什么样的时间你要实现这一点，使用什么？运行SPA，看看它是不是树。它是有效的，而且是最有名的。 – ashley

我不确定SPA是什么。这个问题是从算法第3版的介绍。我想我只需要提供一个通用算法;我不需要指定数据结构。我建议的解决方案在O（E + V）中运行，因为我访问过每个顶点和边，但我不确定它是否正确。 – user1754045

最短路径算法。 Dijkstra的。最着名的算法之一。 – ashley

我认为这会工作

做一个DFS，但不是按照常规图形边缘，只跟随每个顶点的π值。你这样做是为了产生一个拓扑排序，所以第一个要完成的顶点将是拓扑排序中的第一个顶点。请注意，您生成的地形排序中的第一个顶点将是赋予Gaedel算法的“源”顶点。

现在您已经有了一个topo排序，您可以以最有效的顺序放松边界，就像在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 vert都被考虑，并且源顶点匹配。也许。另外，我猜Gaedel的π值引起的前任子图可能会被真正抬高，并且会出现各种各样的疯狂事情，但我认为它不会。

它是O(V + E)，因为外循环运行V次，内循环使用聚合分析运行E次。

来源

2012-11-26 06:06:05 goat

是的，这似乎工作。使用顶级排序查找最短路径图与我正在使用的图相距几段。这个方法将给出正确的起始顶点，并且应该重新创建由prof创建的最短路径图。谢谢您的帮助。 – user1754045

确认为O Dijkstras算法（V + E）

回答

相关问题