直接 Dijkstra 算法的时间复杂度

Question

我很难看到直接实现 Dijkstra 算法（没有堆）的 O(mn) 界限。在我的实现和其他实现中，我发现主循环迭代 n-1 次（对于每个不是源的顶点，n-1），然后在每次迭代中找到最小顶点是 O(n)（检查队列中的每个顶点并找到到源的最小距离）然后每个发现的最小顶点最多有 n-1 个邻居，所以更新所有邻居是 O(n)。在我看来，这会导致 O(n^2) 的界限。下面提供了我的实现

public int[] dijkstra(int s) {
      int[] dist = new int[vNum];
      LinkedList queue = new LinkedList<Integer>();
      for (int i = 0; i < vNum; i++) {
         queue.add(i); // add all vertices to the queue
         dist[i] = Integer.MAX_VALUE; // set all initial shortest paths to max INT value
      }
      dist[s] = 0; // the source is 0 away from itself

      while (!queue.isEmpty()) { // iterates over n - 1 vertices, O(n)

         int minV = getMinDist(queue, dist); // get vertex with minimum distance from source, O(n)
         queue.remove(Integer.valueOf(minV)); // remove Integer object, not position at integer

         for (int neighbor : adjList[minV]) { // O(n), max n edges
            int shortestPath = dist[minV] + edgeLenghts[minV][neighbor];
            if (shortestPath < dist[neighbor]) {
               dist[neighbor] = shortestPath; // a new shortest path have been found
            }
         }
      }

      return dist;

   }

我认为这不正确，但我无法确定 m 因素的影响。

Answer 1

您的实现确实消除了 M 因子，至少如果我们只考虑简单图（两个顶点之间没有多条边）。是 O(N^2)！如果您遍历所有可能的边而不是顶点，复杂度将为 O(N*M)。

编辑：嗯，更具体地说，实际上是 O(M + N^2)。更改某些顶点的值在您的算法中需要 O(1) 时间，并且每次考虑边时都可能发生，换句话说，M 次。这就是为什么复杂度有M的原因。

不幸的是，如果您想使用简单堆，复杂度将是 O(M* log M)（或 M log N）。为什么？您无法快速更改堆中的值。所以如果 dist[v] 突然减少，因为你找到了一条新的、更好的 v 路径，你不能只在堆中改变它，因为你真的不知道它的位置。您可以将 v 的副本放入堆中，但堆的大小将是 O(M)。即使你存储位置并巧妙地更新它，你可能在堆中有 O(N) 个项目，但你仍然必须在每次更改后更新堆，这需要 O(size of heap)。您最多可以更改该值 O(M) 次，这给了您 O(M* log M (or N)) 复杂度

直接 Dijkstra 算法的时间复杂度

Time Complexity of Straight Forward Dijkstra's Algorithm

algorithm

dijkstra

time-complexity