- Dijkstra算法
- 概念
- 算法工作原理
- 代码
参考：https://blog.csdn.net/u011426016/article/details/140895213
Dijkstra算法
Dijkstra算法是一种用于解决单源最短路径问题的贪婪算法。
它的主要目标是在一个有向或无向的、边权重为非负数的图中，找到从一个起始顶点到所有其他顶点的最短路径。
想象一下您正在使用GPS导航，Dijkstra算法就像是导航系统在寻找从您的位置（起始点）到所有可能目的地的最快（或最短）路线。
概念
在理解Dijkstra算法之前，我们需要先了解几个基本的图论概念：
图（Graph）: 由顶点（Vertex）和边（Edge）组成。
顶点（Vertex）: 图中的节点。
边（Edge）: 连接两个顶点的线。
权重（Weight）: 边上的值，代表了通过这条边的“代价”，比如距离、时间或费用。Dijkstra算法要求所有边的权重都必须是非负数。
路径（Path）: 从一个顶点到另一个顶点经过的一系列边。
最短路径（Shortest Path）: 在所有可能的路径中，权重之和最小的那条路径。
算法工作原理
Dijkstra算法的核心思想是：从起点开始，一步步向外“扩张”，每次都选择一个当前已知的、离起点最近的未访问过的顶点，并更新其所有邻居的距离。
类似水波一样逐渐的扩散
步骤：
1.初始化:
创建一个距离字典（或数组），用于存储从起点到每个顶点的当前最短距离。将起点的距离设为0，所有其他顶点的距离设为无穷大（代表目前还无法到达）。
创建一个集合来存放已经访问过的顶点。
使用一个优先队列（Min-Heap）来存储待处理的顶点，队列中的元素是 (距离, 顶点) 的元组，并且总是弹出距离最小的那个。
2.开始循环:
将起点及其距离 (0, start_node) 放入优先队列中。
当优先队列不为空时，重复以下步骤：
3.选择下一个顶点:
从优先队列中取出距离最小的顶点 u。
4.判断访问状态:
如果 u 已经被访问过，则跳过，因为我们已经找到了从起点到 u 的最短路径。
如果 u 未被访问过，将其标记为已访问。
5.更新邻居距离:
遍历 u 的所有邻居 v
计算从起点到 u，再到 v 的新路径距离：new_distance = distance[u] + weight(u, v)。
如果 new_distance 小于目前已知的从起点到 v 的距离 distance[v]，则：
更新 distance[v] 为 new_distance。
将 (new_distance, v) 放入优先队列中。
- 结束
当优先队列为空时，算法结束。此时，距离字典中存储的就是从起点到所有可达顶点的最短路径长度。
代码
import heapqdef dijkstra(graph, start_node):"""使用优先队列实现Dijkstra算法，找到从起始节点到所有其他节点的最短路径。Args:graph: 使用字典表示的图。例如：{'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'C': 2, 'D': 5}, ...}其中，键是节点，值是另一个字典，表示邻居和对应的边权重。start_node: 起始节点的名称。Returns:一个字典，包含从起始节点到所有可达节点的最短距离。"""# 1. 初始化距离字典，将所有距离设置为无穷大，起始点距离为0distances = {node: float('inf') for node in graph}distances[start_node] = 0# 2. 初始化优先队列，将起始节点及其距离放入# 优先队列中的元素是 (距离, 节点)priority_queue = [(0, start_node)]# 3. 存储已访问过的节点visited = set()while priority_queue:# 4. 从优先队列中弹出距离最小的节点current_distance, current_node = heapq.heappop(priority_queue)# 5. 如果当前节点已被访问，跳过if current_node in visited:continue# 6. 标记当前节点为已访问visited.add(current_node)# 7. 遍历当前节点的所有邻居for neighbor, weight in graph[current_node].items():# 计算通过当前节点到达邻居的新距离distance = current_distance + weight# 如果新距离比已知的距离更短，则更新并放入优先队列if distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(priority_queue, (distance, neighbor))return distances# 示例图
# A ---1--- B ---2--- C
# | | \ |
# 4 2 \ 7
# | | \ |
# D ---5--- E ----6---F
# B到E的边权重为3
example_graph = {'A': {'B': 1, 'D': 4},'B': {'A': 1, 'C': 2, 'E': 3},'C': {'B': 2, 'F': 7},'D': {'A': 4, 'E': 5},'E': {'B': 3, 'D': 5, 'F': 6},'F': {'C': 7, 'E': 6}
}# 运行Dijkstra算法，从节点'A'开始
shortest_paths = dijkstra(example_graph, 'A')# 打印结果
print("从节点 'A' 到其他节点的最短距离：")
for node, distance in shortest_paths.items():if distance == float('inf'):print(f" 到节点 {node}: 无法到达")else:print(f" 到节点 {node}: {distance}")
从节点 'A' 到其他节点的最短距离：到节点 A: 0到节点 B: 1到节点 C: 3到节点 D: 4到节点 E: 4到节点 F: 10
就这么简单！！