了解 Dijkstra 算法的简单实现的运行时

Question

我正在绞尽脑汁地了解 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)？

Answer 1

我不是一个大专家，所以对我的回答持保留态度，但我最近才使用了一些路径算法。首先，O() 表示法并不精确，因此例如 -1 在事物的宏伟计划中并不真正相关，等等。在我看来，你有一个 for 循环，这至少是 O(N)，其中 n 代表一个节点（这是一种更好的看待它的方式）。 Dijkstra 的路径应用于网格，其中每个方格都是一个节点，并且该节点与起始节点（通过其邻居）的距离是在您移动时计算的。因此，如果您将顶点视为网格中的节点位置，将边视为距离，则 O(VE) 相当于我刚才描述的 O(N)。在这种情况下，每个节点有 8 个邻居（边），因此除非你有一个很小的网格，否则它不会在 O(N^2) 中运行。然而，在图上，这根本不是真的，您可以拥有一个包含数千个节点的完全连接的图。

我的意思是，如果没有上下文，O() 表示法就毫无意义。

我希望这种思考方式能有所帮助！