Python 实现 Dijkstra 路径规划算法

作者：新兰2024.01.17 22:14浏览量：17

简介：Dijkstra 算法是一种用于解决最短路径问题的图论算法。它通过逐步构建最短路径树，从源节点开始，不断更新所有相邻节点的最短路径长度，最终找到从源节点到目标节点的最短路径。本篇文章将介绍如何使用 Python 实现 Dijkstra 算法，并通过示例来展示其应用。

Dijkstra 算法是一种用于解决最短路径问题的图论算法。它通过逐步构建最短路径树，从源节点开始，不断更新所有相邻节点的最短路径长度，最终找到从源节点到目标节点的最短路径。下面我们将使用 Python 来实现 Dijkstra 算法。
首先，我们需要定义一个类来表示图的数据结构。该类应该包含添加节点和边的方法，以及一个方法来获取给定源节点到目标节点的最短路径。

  1. class Graph:
  2. def __init__(self):
  3. self.graph = {}
  4. def add_node(self, node):
  5. if node not in self.graph:
  6. self.graph[node] = []
  7. def add_edge(self, source, destination, weight):
  8. if source in self.graph:
  9. self.graph[source].append((destination, weight))
  10. else:
  11. self.graph[source] = [(destination, weight)]

接下来，我们实现 Dijkstra 算法的函数。该函数接受图对象、源节点和目标节点作为参数，并返回从源节点到目标节点的最短路径。

  1. def dijkstra(graph, source, target):
  2. # 初始化距离字典，将所有节点距离设置为无穷大，将源节点距离设置为0
  3. distance = {node: float('inf') for node in graph.graph}
  4. distance[source] = 0
  5. # 初始化已访问节点集合
  6. visited = set()
  7. # 创建优先级队列并将源节点加入队列中
  8. queue = [(0, source)]
  9. while queue:
  10. # 取出队列中距离最小的节点
  11. current_distance, current_node = heapq.heappop(queue)
  12. # 如果该节点已访问过，跳过此次循环
  13. if current_node in visited:
  14. continue
  15. # 将当前节点标记为已访问
  16. visited.add(current_node)
  17. # 遍历当前节点的邻居节点
  18. for neighbor, weight in graph.graph[current_node]:
  19. # 计算经过当前节点后的邻居节点距离
  20. distance_through_u = current_distance + weight
  21. # 如果经过当前节点后的邻居节点距离小于之前计算的距离，更新距离字典和最短路径字典
  22. if distance_through_u < distance[neighbor]:
  23. distance[neighbor] = distance_through_u
  24. heapq.heappush(queue, (distance[neighbor], neighbor))
  25. # 在最短路径字典中记录经过的节点和距离
  26. shortest_path = {node: (current_node, distance[node]) for node in visited}
  27. shortest_path[neighbor] = (current_node, distance[neighbor])
  28. return shortest_path, distance[target]  # 返回最短路径和目标节点的距离

最热文章