Dijkstra算法朴素实现的时间复杂度解析及优化疑问

核心问题 #

• 朴素Dijkstra算法的时间复杂度为O(VE)的结论是否正确？
• 提供的C#代码是否属于O(VE)时间复杂度？
• 为何O(V*(V+E))等价于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)（最多执行V次，每个节点加入Computed一次）
• 找最小距离节点的内层循环：O(V)（遍历所有节点）
• 松弛邻边的内层循环：总复杂度O(E)（每条边仅被松弛一次）

问题解答 #

1. 朴素Dijkstra时间复杂度O(VE)是否正确？ #

正确。朴素实现的核心开销来自两部分：

• 每次遍历所有未访问节点找最小距离，执行V次，总开销O(V²)
• 所有边的松弛操作，总开销O(E)
  总复杂度为O(V² + E)。在稠密图场景下，边数E≈V²，此时O(V²+E)=O(V²)=O(VE)；而稀疏图中E远小于V²，但我们通常以最坏情况（稠密图）定义朴素实现的时间复杂度，因此统一记作O(VE)或O(V²)，二者在稠密场景下等价。

2. 提供的代码是否是O(VE)时间复杂度？ #

是的。你的分析准确：

• 外层循环最多执行V次
• 每次外层循环包含O(V)的找最小节点操作，以及累计O(E)的松弛操作
  总复杂度为O(V² + E)，对应最坏情况的O(VE)。

3. 为何O(V*(V+E))等价于O(VE)？ #

首先纠正：实际总复杂度是O(V² + E)，而非O(V*(V+E))——后者是错误的写法，但如果按该式推导，核心原因是渐近复杂度只保留最高阶项：

• 当E≥V时（绝大多数图场景，尤其是稠密图E≈V²），V*(V+E)=V²+VE，其中VE是最高阶项，因此O(V²+VE)=O(VE)
• 当E<V时（极稀疏图），VE<V²，最高阶为V²，但这种场景下不会用朴素Dijkstra，而是选择堆优化版本，因此朴素实现的最坏复杂度仍以稠密图为准，记作O(VE)。

4. 更优的朴素实现方式？ #

朴素实现的瓶颈是「每次找未访问节点的最小距离」，可以通过减少常数开销优化，核心复杂度仍为O(V²+E)：

• 用布尔数组替代HashSet：数组的直接索引访问比HashSet的Contains操作更快，无哈希计算开销
• 简化松弛条件：已访问节点的最短路径已确定，无需判断是否已访问，可直接尝试松弛
• 提前终止：若最小距离为无穷大，直接跳出循环，无需处理不可达节点

优化后的示例代码：

internal void DijkstraShortestPathCompute()
{
    bool[] isVisited = new bool[MAX_VERTEX + 1];
    int[] shortestPath = new int[MAX_VERTEX + 1];
    // 初始化：起点设为0，其余为最大值
    Array.Fill(shortestPath, MAX_VALUE);
    shortestPath[1] = 0; // 假设起点为顶点1

    int visitedCount = 0;
    while (visitedCount < MAX_VERTEX)
    {
        // 寻找未访问的最小距离节点
        int minDist = MAX_VALUE;
        int u = -1;
        for (int j = 1; j <= MAX_VERTEX; j++)
        {
            if (!isVisited[j] && shortestPath[j] < minDist)
            {
                minDist = shortestPath[j];
                u = j;
            }
        }

        if (u == -1) break; // 剩余节点不可达，终止循环

        isVisited[u] = true;
        visitedCount++;

        // 松弛邻边
        foreach ((int v, int weight) in AdjacencyList[u])
        {
            if (shortestPath[u] + weight < shortestPath[v])
            {
                shortestPath[v] = shortestPath[u] + weight;
            }
        }
    }
}

内容的提问来源于stack exchange，提问作者coderLane