迪杰斯特拉算法（Dijkstra）——最短路径问题的贪心解法

迪杰斯特拉算法（Dijkstra）是一种非常有效的求解最短路径问题的贪心算法。该算法以荷兰计算机科学家艾兹格·迪杰斯特拉的名字命名，他于1956年提出了该算法。迪杰斯特拉算法可以用于解决单源最短路径问题，即从一个指定的起点到其他所有顶点的最短路径。
一、迪杰斯特拉算法原理
迪杰斯特拉算法的基本思想是：从起点开始，逐步选择当前距离起点最近的顶点，将其加入已访问集合中，并更新其相邻顶点到起点的最短路径长度。重复此过程，直到所有顶点都被访问。
在选择当前距离起点最近的顶点时，可以使用优先队列（最小堆）来实现。优先队列按照顶点到起点的距离进行排序，距离越小的顶点优先级越高。每次从未访问的顶点中选择优先级最高的顶点进行扩展，并更新其相邻顶点到起点的最短路径长度。
二、迪杰斯特拉算法实现过程
迪杰斯特拉算法的实现过程可以分为以下几个步骤：

1. 初始化：将起点加入已访问集合中，将起点到自身的距离设为0，其他顶点到起点的距离设为无穷大。创建一个优先队列，将所有未访问的顶点加入队列中。
2. 从优先队列中取出距离起点最近的顶点，记为当前顶点。将当前顶点加入已访问集合中。
3. 遍历当前顶点的所有相邻顶点。如果相邻顶点到起点的距离小于已知的距离，则更新距离，并将相邻顶点加入未访问集合中，重新调整优先队列。
4. 重复步骤2和3，直到所有顶点都被访问或者优先队列为空。
5. 输出结果：最终得到的从起点到其他所有顶点的最短路径长度。
   下面是使用Python实现的迪杰斯特拉算法示例代码：

   import heapq
   def dijkstra(graph, start):
   # 初始化距离字典和优先队列
   distances = {vertex: float('inf') for vertex in graph}
   distances[start] = 0
   queue = [(0, start)]
   heapq.heapify(queue)
   while queue:
   # 取出当前距离起点最近的顶点
   current_distance, current_vertex = heapq.heappop(queue)
   if current_distance > distances[current_vertex]:
   continue
   # 遍历当前顶点的所有相邻顶点
   for neighbor, weight in graph[current_vertex].items():
   distance = current_distance + weight
   if distance < distances[neighbor]:
   distances[neighbor] = distance
   heapq.heappush(queue, (distance, neighbor))
   return distances

   其中，graph表示邻接表形式的图，start表示起点顶点。函数返回一个字典，键为顶点，值为从起点到该顶点的最短路径长度。需要注意的是，邻接表中的每个顶点都应该是一个字典，表示与该顶点相邻的顶点和对应的权重。例如，对于一个有4个顶点的图，邻接表可能如下所示：

   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}
   }

   三、应用实例
   下面是一个简单的应用实例，展示如何使用迪杰斯特拉算法求解最短路径问题：
   假设有一个有向图如下：
   A —1—> B —2—> D —3—> E —4—> F —5—> G —6—> H —7—> I —8—> J —9—> K (终点)
   ^ ^ ^ ^
   | | | |
   2 3 4 5
   | | |