### Python 实现 Dijkstra 最短路径算法并进行可视化 以下是基于 Dijkstra 算法的 Python 代码示例，用于计算图中的最短路径，并通过 Matplotlib 库实现路径的可视化。 #### 1. 定义图的数据结构 为了表示加权有向图，可以使用字典嵌套的方式存储邻接表及其对应的权重： ```python graph = { 'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'C': 2, 'D': 5}, 'C': {'A': 4, 'B': 2, 'D': 1}, 'D': {'B': 5, 'C': 1} } ``` 此部分定义了一个简单的带权图，其中键代表节点名称，值是一个子字典，描述了相邻节点及其之间的距离[^1]。 #### 2. 编写 Dijkstra 算法的核心逻辑 下面展示了如何利用优先队列优化 Dijkstra 的核心过程： ```python import heapq def dijkstra(graph, start): distances = {node: float('inf') for node in graph} # 初始化所有节点的距离为无穷大 distances[start] = 0 # 起始节点的距离设为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 ``` 这段代码实现了标准版的 Dijkstra 算法，返回从起始节点到其他各节点的最短距离[^2]。 #### 3. 绘制图形与路径可视化 借助 `networkx` 和 `matplotlib` 工具包完成图的绘制和路径高亮显示功能： ```python import networkx as nx import matplotlib.pyplot as plt def visualize_graph_with_path(graph, path_nodes): G = nx.Graph() edge_labels = {} # 添加所有的边和标签 for node, neighbors in graph.items(): for neighbor, weight in neighbors.items(): if f"{min(node, neighbor)}-{max(node, neighbor)}" not in edge_labels.keys(): G.add_edge(node, neighbor, weight=weight) edge_labels[(node, neighbor)] = weight pos = nx.spring_layout(G) # 布局方式可以选择不同风格如circular,spring等 # 高亮展示指定路径上的节点和边 edges_in_path = [] nodes_in_path = set(path_nodes) for i in range(len(path_nodes)-1): u,v=path_nodes[i],path_nodes[i+1] if v in graph[u]: edges_in_path.append((u,v)) colors = ['red' if e in edges_in_path else 'black' for e in G.edges()] nx.draw(G, pos, with_labels=True, edge_color=colors, width=2, font_weight='bold', node_size=700) # 显示边权重 nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels) plt.show() # 测试调用 start_node = 'A' distances = dijkstra(graph, start_node) print(f"The shortest distances from '{start_node}' are:", distances) # 构造一条可能的最短路径供演示（这里假设已知） shortest_path_example = ['A','B','C'] visualize_graph_with_path(graph, shortest_path_example) ``` 以上脚本不仅执行了寻找最短路径的任务，还提供了直观的结果呈现手段[^3]。