最短路径算法——Dijkstra(迪杰斯特拉)的详细图解与Python实现

作者:carzy2024.01.17 10:44浏览量:35

简介:本文将通过图解和Python代码详细介绍Dijkstra算法的工作原理,包括算法的基本思想、过程、实现方式等。旨在帮助读者深入理解并掌握该算法,并能够在实际项目中运用它。

千帆应用开发平台“智能体Pro”全新上线 限时免费体验

面向慢思考场景,支持低代码配置的方式创建“智能体Pro”应用

立即体验

在计算机科学中,Dijkstra算法是一种用于在有向图中查找单源最短路径的算法。该算法由荷兰计算机科学家艾兹格·迪杰斯特拉(Edsger Dijkstra)于1956年提出,常用于路由、搜索引擎等场景。
一、算法思想
Dijkstra算法的基本思想是逐步构建最短路径树。开始时,将源节点标记为已访问,并选择一个距离源节点最近的节点作为当前节点。然后,将当前节点标记为已访问,并更新其相邻节点的距离。重复这个过程,直到所有节点都被访问。
二、算法过程

  1. 初始化:设置源节点到所有其他节点的距离为无穷大(表示尚未找到路径),将源节点标记为已访问。
  2. 选择一个未访问的节点作为当前节点,该节点到源节点的距离应是最短的。
  3. 更新当前节点的所有相邻节点的距离。如果通过当前节点到达相邻节点的距离小于已知的距离,则更新该距离。
  4. 重复步骤2和3,直到所有节点都被访问。
    三、Python实现
    下面是一个简单的Dijkstra算法的Python实现:
    1. import heapq
    2. def dijkstra(graph, start):
    3. # 初始化距离字典,将所有节点的距离设置为无穷大(未找到路径)
    4. distances = {node: float('infinity') for node in graph}
    5. # 将源节点到自身的距离设置为0
    6. distances[start] = 0
    7. # 使用最小堆来存储待访问节点及其距离
    8. queue = [(0, start)]
    9. while queue:
    10. # 取出当前距离最小的节点
    11. current_distance, current_node = heapq.heappop(queue)
    12. # 如果该节点已经被访问过(即距离已经确定),跳过
    13. if current_distance > distances[current_node]:
    14. continue
    15. # 遍历相邻节点,更新距离
    16. for neighbor, weight in graph[current_node].items():
    17. distance = current_distance + weight
    18. # 如果通过当前节点到达相邻节点的距离更短,则更新距离字典和最小堆
    19. if distance < distances[neighbor]:
    20. distances[neighbor] = distance
    21. heapq.heappush(queue, (distance, neighbor))
    22. return distances
    这个Python代码实现了一个基本的Dijkstra算法。其中,graph参数是一个字典,表示图的邻接表表示。start参数是源节点。函数返回一个字典,表示从源节点到所有其他节点的最短距离。例如:
    1. graph = {
    2. 'A': {'B': 1, 'C': 3},
    3. 'B': {'A': 1, 'C': 2, 'D': 4},
    4. 'C': {'A': 3, 'B': 2, 'D': 1},
    5. 'D': {'B': 4, 'C': 1}
    6. }
    7. start = 'A'
    8. print(dijkstra(graph, start)) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}
    这个例子中,图表示为一个邻接表,其中每个节点是一个字典,表示该节点相邻的节点及其权重。start参数是源节点’A’。函数返回一个字典,表示从源节点到所有其他节点的最短距离。
article bottom image

相关文章推荐

发表评论