一、原理层面代码

from cmath import inf # 导入inf（无穷大）来表示无限大的值

# 构建图 map = {} # 创建一个空的图 map['乐谱'] = {} # 添加节点'乐谱' map['乐谱']['唱片'] = 5 # 在'乐谱'和'唱片'之间添加一条边，权重为5 map['乐谱']['海报'] = 0 # 在'乐谱'和'海报'之间添加一条边，权重为0 map['唱片'] = {} # 添加节点'唱片' map['唱片']['吉他'] = 15 # 在'唱片'和'吉他'之间添加一条边，权重为15 map['唱片']['架子鼓'] = 20 # 在'唱片'和'架子鼓'之间添加一条边，权重为20 map['海报'] = {} # 添加节点'海报' map['海报']['吉他'] = 30 # 在'海报'和'吉他'之间添加一条边，权重为30 map['海报']['架子鼓'] = 35 # 在'海报'和'架子鼓'之间添加一条边，权重为35 map['吉他'] = {} # 添加节点'吉他' map['吉他']['钢琴'] = 20 # 在'吉他'和'钢琴'之间添加一条边，权重为20 map['架子鼓'] = {} # 添加节点'架子鼓' map['架子鼓']['钢琴'] = 10 # 在'架子鼓'和'钢琴'之间添加一条边，权重为10 # 初始化table中的行 def initRow(costs, key, cost): # 初始化每行的信息，包括开销、父节点和是否已经被检查过 costs[key] = {} costs[key]['father'] = None # 最短路径中的前一个节点 costs[key]['cost'] = cost # 当前节点的开销 costs[key]['isChecked'] = False # 当前节点是否已经被检查过 # 获取当前开销最少的节点 def findLowerCostNode(costs): key = None cost = float(inf) # 初始化开销为无穷大 for name in costs: item = costs[name] if item['isChecked'] is False and item['cost'] < cost: cost = item['cost'] key = name return key def dijkstra(map, start, end): # 初始化表 costs = {} # 创建一张表来记录每个节点的开销和父节点 initRow(costs, start, 0) # 初始化起始节点的行 key = findLowerCostNode(costs) # 获取当前开销最小的节点 while key is not None and key != end: # 当存在未检查的节点且未到达终点时 # 获取邻居 neighbors = map[key].keys() # 获取当前节点的所有邻居节点（即它的所有出边） # 检查到邻居的开销 for neighbor in neighbors: # 如果邻居不在costs中，则添加 if neighbor not in costs: initRow(costs, neighbor, float(inf)) # 将邻居节点添加到表中 # 获取到key的开销 newCost = map[key][neighbor] + costs[key]['cost'] # 计算经过当前节点到达邻居节点的开销 # 如果经key到邻居的开销小于已有开销 if newCost < costs[neighbor]['cost']: costs[neighbor]['cost'] = newCost # 更新到达邻居节点的最短路径的开销 costs[neighbor]['father'] = key # 更新到达邻居节点的最短路径上的父节点 # key的所有邻居都检查过了 costs[key]['isChecked'] = True key = findLowerCostNode(costs) # 继续寻找当前开销最小的节点 # 打印最终结果 key = end routes = [] while key is not None: node = costs[key] routes.insert(0, key) father = node['father'] key = father print(f'最短路径为: {"->".join(routes)}，开销{costs[end]["cost"]}') # 使用Dijkstra算法找到从'乐谱'到'钢琴'的最短路径 dijkstra(map, '乐谱', '钢琴')

二、简单代码，使用networkx包

import networkx as nx import matplotlib.pyplot as plt # #​ 创建有向图 # graph = nx.DiGraph() # # #​ 添加有向边 # graph.add_edge('A', 'B', weight=1) # graph.add_edge('A', 'C', weight=3) # graph.add_edge('B', 'C', weight=1) # graph.add_edge('B', 'D', weight=2) # graph.add_edge('C', 'D', weight=1) # graph.add_edge('D', 'E', weight=3) # 创建无向图 graph = nx.Graph() # 添加无向边 graph.add_edge('A', 'B', weight=12) graph.add_edge('A', 'F', weight=16) graph.add_edge('A', 'G', weight=14) graph.add_edge('B', 'C', weight=10) graph.add_edge('B', 'F', weight=7) graph.add_edge('C', 'D', weight=3) graph.add_edge('C', 'E', weight=5) graph.add_edge('C', 'F', weight=5) graph.add_edge('D', 'E', weight=4) graph.add_edge('E', 'F', weight=2) graph.add_edge('E', 'G', weight=8) graph.add_edge('F', 'G', weight=9) # 计算最短路径 path = nx.dijkstra_path(graph, 'A', 'D') # 输出路径 print(path) # 绘制图形 pos = nx.spring_layout(graph) nx.draw_networkx_nodes(graph, pos) nx.draw_networkx_edges(graph, pos) nx.draw_networkx_labels(graph, pos) nx.draw_networkx_edge_labels(graph, pos, edge_labels={(u, v): d['weight'] for u, v, d in graph.edges(data=True)}) nx.draw_networkx_edges(graph, pos, edgelist=[(path[i], path[i + 1]) for i in range(len(path) - 1)], edge_color='r', width=2) plt.show()