迪杰斯特拉（Dijkstra）最短路径算法
迪杰斯特拉算法是一种用于解决带权有向图中单源最短路径问题的算法。该算法由荷兰计算机科学家艾兹格·迪杰斯特拉于1956年提出。它通过逐步迭代，找到从源节点到其他所有节点的最短路径。
算法原理
- 初始化：将源节点的距离设为0，其他所有节点的距离设为无穷大。创建一个空的已访问节点集合。
- 选择最小距离节点：从未访问节点集合中选择距离最小的节点，将其加入到已访问节点集合中。
- 更新邻居节点距离：对于当前节点的所有邻居节点，如果通过当前节点到达邻居节点的距离比原来更短，则更新邻居节点的距离。
- 迭代：重复步骤2和3，直到所有节点都被访问。
代码示例（Python）
代码语言：python代码运行次数：0复制import heapq
def dijkstra(graph, start):
# 初始化距离字典和已访问节点集合
distances = {node: float('infinity') for node in graph}
distances[start] = 0
visited = set()
# 使用最小堆来存储待访问节点及其距离
pq = [(0, start)]
while pq:
# 弹出距离最小的节点
current_distance, current_node = heapq.heappop(pq)
# 如果节点已访问，则跳过
if current_node in visited:
continue
visited.add(current_node)
# 更新邻居节点的距离
for neighbor, weight in graph[current_node].items():
distance = current_distance weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances时间复杂度与优化
- 时间复杂度：迪杰斯特拉算法的时间复杂度为O((V E)logV)，其中V是顶点数，E是边数。在最坏情况下，所有节点和边都需要被处理。
- 优化：使用优先队列（如最小堆）来存储待访问节点，以便在常数时间内找到距离最小的节点。这可以显著提高算法效率。
应用场景与限制
- 应用场景：迪杰斯特拉算法被广泛应用于网络路由、地图导航、物流配送等领域。它可以有效地找到从一个节点到其他所有节点的最短路径。
- 限制：迪杰斯特拉算法不能处理带有负权边的图。对于带有负权边的图，可以使用贝尔曼-福特（Bellman-Ford）算法或其他相关算法。
