贪心算法——最短路径问题Dijkstra算法

贪心算法是一种在每一步选择中都采取当前最优的选择，从而希望导致结果是全局最优的算法。Dijkstra算法是贪心算法的一种应用，用于解决最短路径问题。
Dijkstra算法的基本思想是从一个起始节点开始，逐步找到从该节点到其他所有节点的最短路径。算法的主要步骤如下：

1. 创建一个距离数组，用于存储从起始节点到各个节点的最短距离。初始时，将起始节点到自身的距离设为0，其他节点的距离设为无穷大。
2. 从未访问过的节点中选择一个距离最小的节点，将其标记为已访问。
3. 更新从起始节点到已访问节点的所有邻居节点的距离。如果通过当前已访问节点到达邻居节点的距离小于之前计算的距离，则更新距离数组。
4. 重复步骤2和3，直到所有节点都被访问过。
   下面是一个简单的Python代码实现Dijkstra算法：

   import sys
   import heapq
   def dijkstra(graph, start):
   # 初始化距离数组
   distances = {node: float('inf') for node in graph}
   distances[start] = 0
   # 创建优先队列，用于存储未访问节点和对应的距离
   priority_queue = [(0, start)]
   while priority_queue:
   # 取出当前距离最小的节点
   current_distance, current_node = heapq.heappop(priority_queue)
   # 如果该节点已被访问过，跳过
   if current_distance > distances[current_node]:
   continue
   # 遍历邻居节点
   for neighbor, weight in graph[current_node].items():
   distance = current_distance + weight
   if distance < distances[neighbor]:
   distances[neighbor] = distance
   heapq.heappush(priority_queue, (distance, neighbor))
   return distances

   在上面的代码中，我们首先初始化一个距离数组，将所有节点的距离设为无穷大，除了起始节点的距离设为0。然后创建一个优先队列，用于存储未访问节点和对应的距离。接下来，我们不断从优先队列中取出当前距离最小的节点，并更新其邻居节点的距离。最后返回计算得到的距离数组。
   下面是一个使用Dijkstra算法解决实际问题的例子：
   假设我们有一个带权重的有向图，表示为一个字典的字典，其中外层字典的键表示节点，内层字典表示与该节点相邻的节点及其对应的权重。我们可以使用Dijkstra算法找到从起始节点到其他所有节点的最短路径。例如：

   graph = {
   'A': {'B': 1, 'C': 3},
   'B': {'A': 1, 'C': 2, 'D': 4},
   'C': {'A': 3, 'B': 2, 'D': 1},
   'D': {'B': 4, 'C': 1}
   }
   start = 'A'
   shortest_paths = dijkstra(graph, start)
   print(shortest_paths) # 输出 {'A': 0, 'B': 1, 'C': 3, 'D': 4}

   在上面的例子中，我们定义了一个带权重的有向图，并使用Dijkstra算法找到了从起始节点’A’到其他所有节点的最短路径。输出的结果是一个字典，其中键是节点，值是从起始节点到该节点的最短距离。