我正在绞尽脑汁地了解 Dijsktra 算法的朴素(无堆)实现的运行时,以及可能是否有更好的代码用于这种朴素的实现。
理论上朴素实现提到的运行时间是 O(VE),其中 E 是边数,V 是顶点数。这是正确的还是我读错了?以下代码运行时间为 O(VE) 吗?如何?有没有更好的方法来简单地实现这个?
internal void DijkstraShortestPathCompute()
{
// initialize shortest paths for s being 0 and rest as indefinite
// loop until all vertices are explored: hashset condition
// loop all the vertices: 1 -> N
// find unexplored and vertex with smallest edge
// if no smallest edge disconnect and break
// Add to hashset
// relax its neighbors - update the length of each neighbor if they aren't seen and their current distance smaller than prev
// while all vertices are not explored
while(Computed.Count < MAX_VERTEX)
{
// find the smallest edge
(int w, int lvw) = (-1, MAX_VALUE);
for(int j = 1; j <= MAX_VERTEX; j++)
{
// only if its not computed before and its dijsktra score is the smalles
if(!Computed.Contains(j) && ShortestPath[j] < lvw)
{
lvw = ShortestPath[j];
w = j;
}
}
// disconnected graph - walk out
if(w == -1)
break;
// add it to the explored space
Computed.Add(w);
// forward relax the edges so that next iteration we can find the smallest potential edges
foreach((int n, int l) in AdjacencyList[w])
{
// if it is not visited and its calculated distance is smallest only then update
if(!Computed.Contains(n) && ShortestPath[w] + l < ShortestPath[n])
ShortestPath[n] = ShortestPath[w] + l;
}
}
}
我可以看到我们正在 O(V-1) 中运行外部以下循环,其中 V 是顶点数
while(Computed.Count < MAX_VERTEX)
以下第一个内循环需要 O(V) 次
for(int j = 1; j <= MAX_VERTEX; j++)
第二个内部循环需要 O(E) 次,其中 E 是边数
foreach((int n, int l) in AdjacencyList[w])
为什么 O(V-1 (V + E)) 等于 O(VE)?
我不是一个大专家,所以对我的回答持保留态度,但我最近才使用了一些路径算法。首先,O() 表示法并不精确,因此例如 -1 在事物的宏伟计划中并不真正相关,等等。在我看来,你有一个 for 循环,这至少是 O(N),其中 n 代表一个节点(这是一种更好的看待它的方式)。 Dijkstra 的路径应用于网格,其中每个方格都是一个节点,并且该节点与起始节点(通过其邻居)的距离是在您移动时计算的。因此,如果您将顶点视为网格中的节点位置,将边视为距离,则 O(VE) 相当于我刚才描述的 O(N)。在这种情况下,每个节点有 8 个邻居(边),因此除非你有一个很小的网格,否则它不会在 O(N^2) 中运行。然而,在图上,这根本不是真的,您可以拥有一个包含数千个节点的完全连接的图。
我的意思是,如果没有上下文,O() 表示法就毫无意义。
我希望这种思考方式能有所帮助!