Dijkstra 算法时间复杂度

Dijkstra算法时间复杂度分析
对于Dijkstra算法而言，存在两种主要形式：朴素版和堆优化版。
朴素Dijkstra算法
该版本适用于稠密图，在每次迭代过程中都需要遍历所有节点来寻找当前距离最小的未访问节点。因此，其时间复杂度为 O(n²)[^1]，这里 n 表示节点的数量。
def dijkstra_naive(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0

visited = set()

while len(visited) != len(graph):
current_node = min(
(node for node in graph if node not in visited),
key=lambda x: dist[x]
)

visited.add(current_node)

for neighbor, weight in graph[current_node].items():
new_dist = dist[current_node] + weight

if new_dist < dist[neighbor]:
dist[neighbor] = new_dist

return dist
登录后复制
堆优化Dijkstra算法
通过引入二叉堆或其他类型的优先队列结构可以显著降低查找最小距离节点所需的成本。这种改进使得每一步仅需对数时间内完成更新操作，从而整体性能提升至 O(m log n)，m 是边的数量，n 是节点数目[^3]。
import heapq

def dijkstra_heapq(graph, start):
pq = [(0, start)] # priority queue with tuple (distance, vertex)
distances = {}

while pq:
cur_distance, u = heapq.heappop(pq)

if u in distances:
continue

distances[u] = cur_distance

for v, w in graph[u].items():
if v not in distances:
next_item = cur_distance + w
heapq.heappush(pq, (next_item, v))

return distances
登录后复制