点击上方“进修编程”，选择“星标”公众号
超级无敌干货，第一时间送达！！！
简介：本文将向您介绍一个使用 Dijkstra 算法在加权图中查找最短路径的 Python 脚本。我们还将使用 Matplotlib 和 NetworkX 可视化图形和所采用的路径。此外，我们将为 Mario 制作动画，使其沿着计算出的最短路径移动。
Dijkstra 算法：一种用于查找图中节点之间最短路径的有效算法，例如，该图可表示道路网络。该算法的工作原理是迭代地选择已知距离最小的节点，更新其相邻节点的成本，并在知道最短路径后将节点标记为“已访问”。
使用的库：
networkx：创建和操作图形。
matplotlib：用于绘制图形和创建动画。
heapq：高效实现Dijkstra优先级队列。
numpy：用于数值运算。
matplotlib.image：用于加载马里奥的图像。
matplotlib.path和matplotlib.patches：用于绘制弯曲边缘。
图形定义：
我们首先使用邻接表表示来定义我们的图。每个节点都有一个包含其邻居的字典，其中包含相应的边权重。
import networkx as nximport matplotlib.pyplot as pltimport matplotlib.animation as animationimport heapqimport matplotlib.image as mpimgimport numpy as npfrom matplotlib.path import Pathfrom matplotlib.patches import PathPatchfrom matplotlib.offsetbox import OffsetImage, AnnotationBbox# Updated graph with new weightsgraph = {1: {2: 6, 3: 2, 5: 1},2: {1: 6, 3: 5, 4: 1},3: {1: 2, 2: 3, 4: 1},4: {2: 1, 3: 4, 5: 2},5: {1: 1, 4: 2}}# Create the networkx graph with updated weightsG = nx.Graph()for node, neighbors in graph.items():for neighbor, weight in neighbors.items():G.add_edge(node, neighbor, weight=weight)
Dijkstra 算法：
Dijkstra 算法可找到从起始节点到图中所有其他节点的最短路径。该算法使用优先级队列首先探索最近的节点。
# Dijkstra's Algorithmdef dijkstra(graph, start):queue, visited, min_dist = [(0, start)], set(), {start: 0}prev = {start: None}while queue:(cost, node) = heapq.heappop(queue)if node not in visited:visited.add(node)for neighbor, weight in graph[node].items():new_cost = cost + weightif neighbor not in min_dist or new_cost < min_dist[neighbor]:min_dist[neighbor] = new_costheapq.heappush(queue, (new_cost, neighbor))prev[neighbor] = nodereturn min_dist, prev
重建路径：
从 Dijkstra 算法创建的前驱字典中追溯路径
# Function to reconstruct the path from the predecessor dictionarydef get_path(prev, start, end):path = []while end is not None:path.append(end)end = prev[end]path.reverse()return path
计算 Dijkstra 最短路径：
我们计算从节点 1 到所有其他节点的最短路径：
# Comppute Dijkstra's shortest paths from node 1shortest_paths, prev = dijkstra(graph, 1)print("Shortest paths:", shortest_paths)
创建组合路径：
为了确保所有节点都被访问，我们通过迭代查找到最近未访问节点的最短路径来创建组合路径：
# Create a combined path to visit all nodesall_nodes = list(graph.keys())combined_path = []# Start at node 1current_node = 1visited_nodes = set()while len(visited_nodes) < len(all_nodes):shortest_paths, prev = dijkstra(graph, current_node)next_node = min((node for node in all_nodes if node not in visited_nodes), key=lambda x: shortest_paths[x])path_segment = get_path(prev, current_node, next_node)if combined_path:combined_path.extend(path_segment[1:])else:combined_path.extend(path_segment)visited_nodes.update(path_segment)current_node = next_nodeprint("Combined Path:", combined_path)
可视化：
我们使用 Matplotlib 将图形和 Mario 沿路径的移动可视化。我们定义函数来绘制图形、节点和边，并为 Mario 的移动制作动画。
# Visualization with 2D Graphfig, ax = plt.subplots(figsize=(7, 7)) # Increase figsize to adjust layout size# Set positions manually to form a pentagonpos = {1: (0, 1),2: (np.sin(2 * np.pi / 5), np.cos(2 * np.pi / 5)),3: (np.sin(4 * np.pi / 5), -np.cos(np.pi / 5)),4: (-np.sin(4 * np.pi / 5), -np.cos(np.pi / 5)),5: (-np.sin(2 * np.pi / 5), np.cos(2 * np.pi / 5))}labels = nx.get_edge_attributes(G, 'weight')# Function to draw curved edgesdef draw_curved_edges(ax, G, pos):for (u, v, d) in G.edges(data=True):u_pos = np.array(pos[u])v_pos = np.array(pos[v])control_point = (u_pos + v_pos) / 2 + np.array([0.1, 0.1]) # Control point for curvepath_data = [(Path.MOVETO, pos[u]),(Path.CURVE3, control_point),(Path.CURVE3, pos[v])]codes, verts = zip(*path_data)path = Path(verts, codes)patch = PathPatch(path, facecolor='none', edgecolor='black', linewidth=2)ax.add_patch(patch)def draw_nodes(ax, pos):nx.draw(G, pos, with_labels=True, node_color='skyblue', node_size=1400, ax=ax) # Increased node_size# Function to draw the entire graphdef draw_graph(ax, G, pos):draw_nodes(ax, pos)draw_curved_edges(ax, G, pos)nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, ax=ax)# Load the image of Marioimg = mpimg.imread("C:/Users/schintala/Desktop/mario.png")# Function to mark the pathdef mark_path(ax, path, pos):for i in range(len(path)-1):u_pos = np.array(pos[path[i]])v_pos = np.array(pos[path[i+1]])control_point = (u_pos + v_pos) / 2 + np.array([0.1, 0.1]) # Control point for curvepath_data = [(Path.MOVETO, pos[path[i]]),(Path.CURVE3, control_point),(Path.CURVE3, pos[path[i+1]])]codes, verts = zip(*path_data)path_patch = Path(verts, codes)patch = PathPatch(path_patch, facecolor='none', edgecolor='red', linewidth=4)ax.add_patch(patch)def update(num):ax.clear()draw_graph(ax, G, pos)mark_path(ax, combined_path[:num+1], pos)if num < len(combined_path):x, y = pos[combined_path[num]]imagebox = OffsetImage(img, zoom=0.1)ab = AnnotationBbox(imagebox, (x, y), frameon=False)ax.add_artist(ab)return ax,ani = animation.FuncAnimation(fig, update, frames=len(combined_path), blit=False, interval=1000)ani.save('dijkstra_animation.gif', writer='pillow') # Save as GIF using Pillow writerplt.show()
解释：
图定义：我们使用邻接表定义图，其中每个节点指向其邻居和相应的边权重。然后使用此图创建 NetworkX 图。
Dijkstra 算法：我们使用优先级队列来实现 Dijkstra 算法，以跟踪从起始节点到每个节点的最小距离。该算法还维护一个前任字典来重建最短路径。
路径重建：该get_path函数利用前驱字典追溯从终点节点到起点节点的路径。
组合路径：我们通过迭代查找到最近未访问节点的最短路径来创建访问所有节点的组合路径。
可视化：我们使用 Matplotlib 将图形和路径可视化。我们定义函数来绘制图形、节点和曲线边缘。我们还使用 Matplotlib 的动画功能为 Mario 沿路径的移动制作动画。
结论：
该脚本不仅使用 Dijkstra 算法在加权图中查找最短路径，而且还将图形可视化，并使用 Mario 的图像以动画形式呈现路径的遍历。此可视化有助于更好地理解算法及其在现实场景中的应用。
python、matlab程序设计找我。
— 完 —
