【附源码】Python ：校园导航与最短路径算法

系列文章目录

Python 算法学习：校园导航与最短路径算法

前言

这段代码是一个使用Python编写的校园导航程序，它利用tkinter库创建图形用户界面(GUI)，networkx库处理图和路径查找，以及matplotlib进行图形的绘制和展示。不过要注意的是，因为笔者没有固定路径的长度，所以图像的形状为随机。

一、代码需求

编写一个python可视化的校园导航，要求可以输入起点和终点来找出最短路径

二、使用步骤

1.引入库

代码如下（示例）：

import tkinter as tk
from tkinter import simpledialog
import networkx as nx
import matplotlib.pyplot as plt
from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg
from pylab import mpl
# 设置显示中文字体
mpl.rcParams["font.sans-serif"] = ["SimHei"]
# 创建校园地图的图结构
G = nx.Graph()

2.设置图中地点与对应关系

代码如下（示例）：

# 假设的校园地点
locations = ["图书馆", "教学楼A", "教学楼B", "教学楼C","食堂A", "食堂B","宿舍区A", "宿舍区B", "宿舍区C", "宿舍区D","体育馆"
]# 地点之间的连接关系
# 教学楼到图书馆和体育馆连通
edges = [("教学楼A", "图书馆"), ("教学楼A", "体育馆"),("教学楼B", "图书馆"), ("教学楼B", "体育馆"),("教学楼C", "图书馆"), ("教学楼C", "体育馆"),
]# 食堂到宿舍区连通
for canteen in ["食堂A", "食堂B"]:for dorm in ["宿舍区A", "宿舍区B", "宿舍区C", "宿舍区D"]:edges.append((canteen, dorm))# 体育馆到图书馆连通
edges.append(("体育馆", "图书馆"))# 其他可能的连接，例如图书馆到所有地点
for location in locations:if location != "图书馆":edges.append(("图书馆", location))# 添加节点和边
G.add_nodes_from(locations)
G.add_edges_from(edges)# 布局图结构
pos = nx.spring_layout(G)

3.编写最短路径算法

代码如下（示例）：

# 找到最短路径的函数
def shortest_path(G, start, end):try:return nx.shortest_path(G, source=start, target=end)except nx.NetworkXNoPath:return None# 设置起点和终点的函数
def set_start():global start_pointstart_point = simpledialog.askstring("起点", "请输入起点:")def set_end():global end_pointend_point = simpledialog.askstring("终点", "请输入终点:")# 绘制最短路径
def draw_path():global axif start_point and end_point:path = shortest_path(G, start_point, end_point)if path:print(f"从 {start_point} 到 {end_point} 的最短路径是: {path}")ax.clear()nx.draw(G, pos, ax=ax, with_labels=True)nx.draw_networkx_nodes(G, pos, nodelist=path, node_color='red')nx.draw_networkx_edges(G, pos, edgelist=[(path[i], path[i+1]) for i in range(len(path)-1)], edge_color='red')canvas.draw()else:print(f"没有从 {start_point} 到 {end_point} 的路径。")

4.编写对应的窗口与控件

代码如下（示例）：

# 创建主窗口
root = tk.Tk()
root.title("校园导航")# 设置窗口在显示时置顶
root.attributes('-topmost', 1)# 创建画布
fig, ax = plt.subplots(figsize=(10, 10))
canvas = FigureCanvasTkAgg(fig, master=root)
canvas_widget = canvas.get_tk_widget()
canvas_widget.pack(side=tk.TOP, fill=tk.BOTH, expand=True)# 初始绘制图
nx.draw(G, pos, ax=ax, with_labels=True)# 创建按钮
start_button = tk.Button(root, text="设置起点", command=set_start)
start_button.pack(side=tk.LEFT)end_button = tk.Button(root, text="设置终点", command=set_end)
end_button.pack(side=tk.LEFT)path_button = tk.Button(root, text="显示最短路径", command=draw_path)
path_button.pack(side=tk.LEFT)# 运行主循环
root.mainloop()

三、源码展示

import tkinter as tk
from tkinter import simpledialog
import networkx as nx
import matplotlib.pyplot as plt
from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg
from pylab import mpl
# 设置显示中文字体
mpl.rcParams["font.sans-serif"] = ["SimHei"]
# 创建校园地图的图结构
G = nx.Graph()# 假设的校园地点
locations = ["图书馆", "教学楼A", "教学楼B", "教学楼C","食堂A", "食堂B","宿舍区A", "宿舍区B", "宿舍区C", "宿舍区D","体育馆"
]# 地点之间的连接关系
# 教学楼到图书馆和体育馆连通
edges = [("教学楼A", "图书馆"), ("教学楼A", "体育馆"),("教学楼B", "图书馆"), ("教学楼B", "体育馆"),("教学楼C", "图书馆"), ("教学楼C", "体育馆"),
]# 食堂到宿舍区连通
for canteen in ["食堂A", "食堂B"]:for dorm in ["宿舍区A", "宿舍区B", "宿舍区C", "宿舍区D"]:edges.append((canteen, dorm))# 体育馆到图书馆连通
edges.append(("体育馆", "图书馆"))# 其他可能的连接，例如图书馆到所有地点
for location in locations:if location != "图书馆":edges.append(("图书馆", location))# 添加节点和边
G.add_nodes_from(locations)
G.add_edges_from(edges)# 布局图结构
pos = nx.spring_layout(G)# 找到最短路径的函数
def shortest_path(G, start, end):try:return nx.shortest_path(G, source=start, target=end)except nx.NetworkXNoPath:return None# 设置起点和终点的函数
def set_start():global start_pointstart_point = simpledialog.askstring("起点", "请输入起点:")def set_end():global end_pointend_point = simpledialog.askstring("终点", "请输入终点:")# 绘制最短路径
def draw_path():global axif start_point and end_point:path = shortest_path(G, start_point, end_point)if path:print(f"从 {start_point} 到 {end_point} 的最短路径是: {path}")ax.clear()nx.draw(G, pos, ax=ax, with_labels=True)nx.draw_networkx_nodes(G, pos, nodelist=path, node_color='red')nx.draw_networkx_edges(G, pos, edgelist=[(path[i], path[i+1]) for i in range(len(path)-1)], edge_color='red')canvas.draw()else:print(f"没有从 {start_point} 到 {end_point} 的路径。")# 创建主窗口
root = tk.Tk()
root.title("校园导航")# 设置窗口在显示时置顶
root.attributes('-topmost', 1)# 创建画布
fig, ax = plt.subplots(figsize=(10, 10))
canvas = FigureCanvasTkAgg(fig, master=root)
canvas_widget = canvas.get_tk_widget()
canvas_widget.pack(side=tk.TOP, fill=tk.BOTH, expand=True)# 初始绘制图
nx.draw(G, pos, ax=ax, with_labels=True)# 创建按钮
start_button = tk.Button(root, text="设置起点", command=set_start)
start_button.pack(side=tk.LEFT)end_button = tk.Button(root, text="设置终点", command=set_end)
end_button.pack(side=tk.LEFT)path_button = tk.Button(root, text="显示最短路径", command=draw_path)
path_button.pack(side=tk.LEFT)# 运行主循环
root.mainloop()

总结

整体来看，这段代码提供了一个基本的校园导航工具，用户可以通过GUI输入起点和终点，程序计算并展示最短路径。不过，代码中存在一些未使用的导入（如pylab），并且实际应用中可能需要更复杂的逻辑来处理地点之间的实际连接关系。