求解基于优先队列的Dijkstra算法最佳情况时间复杂度

已知使用二叉堆实现优先级队列的Dijkstra算法，最坏情况时间复杂度为O((V + E) log V)，以下是其最佳情况的分析：

最佳情况场景 #

当图满足以下条件时，算法进入最优执行状态：

• 每个节点仅被加入优先级队列一次，即首次计算得到的邻居距离就是最短路径，无需后续更新后重新入队
• 所有边权重均为正（符合Dijkstra算法的适用前提）

典型场景包括：

• 源节点直接连接所有其他节点的星型图，且直接边的权重就是最短路径
• 边权重单调递增的链式线性图，每个节点仅需一次处理即可确定最短路径

最佳情况时间复杂度计算 #

在该场景下：

1. 优先级队列操作：共执行V次入队（enqueue）和V次出队（dequeue）操作，每次操作耗时O(log V)，总耗时为O(V log V)
2. 边遍历操作：遍历所有E条边，每条边仅需一次距离检查与可能的更新，耗时为O(E)

因此，最佳情况的时间复杂度为O(V log V + E)

注：若使用斐波那契堆实现优先级队列，最佳情况时间复杂度仍为O(V log V + E)，且最坏情况可优化至O(V log V + E)，但斐波那契堆因实现复杂度高，实际工程中很少使用。

附：修正后的Dijkstra算法伪代码 #

function Dijkstra(Graph, source):
    // Initialize distances to all nodes as infinity, except for the source node.
    distances = map infinity to all nodes
    distances[source] = 0

    // Initialize an empty set of visited nodes and a priority queue to keep track of the nodes to visit.
    visited = empty set
    queue = new PriorityQueue()
    queue.enqueue(source, 0)

    // Loop until all nodes have been visited.
    while queue is not empty:
        // Dequeue the node with the smallest distance from the priority queue.
        current = queue.dequeue()

        // If the node has already been visited, skip it.
        if current in visited:
            continue

        // Mark the node as visited.
        visited.add(current)

        // Check all neighboring nodes to see if their distances need to be updated.
        for neighbor in Graph.neighbors(current):
            // Calculate the tentative distance to the neighbor through the current node.
            tentative_distance = distances[current] + Graph.distance(current, neighbor)
            // If the tentative distance is smaller than the current distance to the neighbor, update the distance.
            if tentative_distance < distances[neighbor]:
                distances[neighbor] = tentative_distance

                // Enqueue the neighbor with its new distance to be considered for visitation in the future.
                queue.enqueue(neighbor, distances[neighbor])

    // Return the calculated distances from the source to all other nodes in the graph.
    return distances

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