# -*- encoding: utf-8 -*- from head import * from NODE import * from EDGE import * N = Node() E = Edge() class Solve: def __init__(self): self.ans = [] # 记录答案 self.mutians = [] # 若有多个最短路，则保存在mutians中 self.way_sum = 0 # 记录遍历的路径数目 self.minn = float("inf")#初始化最小值为正无穷 self.start = 0 # 起始点 self.end = 0 # 终点 self.mark = [] # 记录该点是否已经经过 self.user_cur = 0 # 记录用户所在点 self.cura = -1 # 记录用户选择的第一个点 self.curb = -1 # 记录用户选择的第二个点 self.con = 0 # 记录必经的节点数目 def Edge_mark_clear(self): for edge in d.Edges: edge[4] = 0 G.draw() def Solve_display(self): for w in frame_right.winfo_children(): w.destroy() # 清除右侧组件 self.Edge_mark_clear() cura = "无" cur1 = -1 curb = "无" cur2 = -1 lab = tk.Label(frame_right, text="自动判断相关", bg=RED, fg=BLACK, font=('微软雅黑', 20)) lab.place(relx=0.18, rely=0.02, width=200, height=30) for i in d.Nodes: if i[2] == 1: cura = str(i[1]) cur1 = i[0] if i[2] == 2: curb = str(i[1]) cur2 = i[0] y0 = 0.1 B = tk.Button(frame_right, text="查询该图是否联通", command=lambda: self.check()) B.place(relx=0.1, rely=0.0 + y0, width=150, height=30) B = tk.Button(frame_right, text="自动求解最优路径-遍历", command=lambda: self.dfs_panel()) B.place(relx=0.1, rely=0.1 + y0, width=200, height=30) B = tk.Button(frame_right, text="自动求解最优路径-贪心", command=lambda: self.greedy_panel()) B.place(relx=0.1, rely=0.15 + y0, width=200, height=30) # B.place(relx=0.1, rely=0.0 + y0, width=150, height=30) B = tk.Button(frame_right, text="自动求解最优路径(包含非必经点)", command=lambda: self.dfs_panel_condition()) B.place(relx=0.1, rely=0.2 + y0, width=200, height=30) # 当前两个节点信息 y0 = 0.4 laba1 = tk.Label(frame_right, text="当前节点1:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) laba2 = tk.Label(frame_right, text=f"{cura}", bg=BLUE, fg=BLACK, font=('微软雅黑', 8)) laba1.place(relx=0.05, rely=0.02 + y0, width=80, height=30) laba2.place(relx=0.35, rely=0.02 + y0, width=50, height=30) labb1 = tk.Label(frame_right, text="当前节点2:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) labb2 = tk.Label(frame_right, text=f"{curb}", bg=BLUE, fg=BLACK, font=('微软雅黑', 8)) labb1.place(relx=0.52, rely=0.02 + y0, width=80, height=30) labb2.place(relx=0.82, rely=0.02 + y0, width=50, height=30) B = tk.Button(frame_right, text="查询两节点是否联通", command=lambda: self.run_graph_check()) B.place(relx=0.1, rely=0.1 + y0, width=250, height=30) B = tk.Button(frame_right, text="查询两节点之间最优路径(时间)", command=lambda: self.auto_lowest_time()) B.place(relx=0.1, rely=0.15 + y0, width=250, height=30) B = tk.Button(frame_right, text="查询两节点之间最优路径(距离)", command=lambda: self.auto_lowest_cost()) B.place(relx=0.1, rely=0.2 + y0, width=250, height=30) B = tk.Button(frame_right, text="查询两节点之间最优路径(含必经节点)", command=lambda: self.auto_lowest_cost_condition()) B.place(relx=0.1, rely=0.25 + y0, width=250, height=30) def run_graph_check(self): a = -1 b = -1 # 根据已有数据获得a，b点的编号 for node in d.Nodes: if node[2] == 1: a = node[0] if node[2] == 2: b = node[0] if a == -1 or b == -1: tk.messagebox.askokcancel(title='错误', message='未选择节点') return self.graph_check(a, b) def graph_check(self, a, b): # 检查A点B点是否互通 find = []# 使用并查集来检测a，b点是否互通 for i in range(len(d.Nodes)):# 初始化并查集 find.append(i)#使得find[i]=i for edge in d.Edges:#根据已有的边来更新并查集 if (edge[8] == 1 and edge[3] == 0): continue x = edge[1] y = edge[2] while not x == find[x]: x = find[x] while not y == find[y]: y = find[y] if x < y: find[y] = x else: find[x] = y x = a y = b while not x == find[x]:#查询a点所在集合 x = find[x] while not y == find[y]:#查询b点所在集合 y = find[y] if find[x] == find[y]:# 输出检查结果 tk.messagebox.askokcancel(title='结果', message='节点 ' + str(a + 1) + '与节点 ' + str(b + 1) + '互通') else: tk.messagebox.askokcancel(title='结果', message='节点 ' + str(a + 1) + '与节点 ' + str(b + 1) + '不互通') def node_mark1(self, name): if name >= len(d.Nodes): N.node_404(name) return for node in d.Nodes: if node[0] == name: node[2] = 1 elif node[2] == 1: node[2] = 0 G.draw() self.Solve_display() def node_mark2(self, name): if name >= len(d.Nodes): N.node_404(name) return for node in d.Nodes: if node[0] == name: node[2] = 2 elif node[2] == 2: node[2] = 0 G.draw() self.Solve_display() def auto_lowest_time(self): # 标记遍历路径 for w in frame_right.winfo_children(): w.destroy() # 清除右侧组件 a = -1 b = -1 for node in d.Nodes: if node[2] == 1: a = node[0] if node[2] == 2: b = node[0] if a == -1 or b == -1: tk.messagebox.askokcancel(title='错误', message='未选择节点') return self.cura = a self.curb = b y0 = 0.1 self.lowest_time_dfs() # print(self.ans) laba1 = tk.Label(frame_right, text="起点:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) laba2 = tk.Label(frame_right, text=f"{d.Nodes[self.cura][1]}", bg=BLUE, fg=BLACK, font=('微软雅黑', 8)) laba1.place(relx=0.05, rely=0.02 + y0, width=80, height=30) laba2.place(relx=0.35, rely=0.02 + y0, width=50, height=30) labb1 = tk.Label(frame_right, text="终点:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) labb2 = tk.Label(frame_right, text=f"{d.Nodes[self.curb][1]}", bg=BLUE, fg=BLACK, font=('微软雅黑', 8)) labb1.place(relx=0.52, rely=0.02 + y0, width=80, height=30) labb2.place(relx=0.82, rely=0.02 + y0, width=50, height=30) y0 += 0.1 lab1 = tk.Label(frame_right, text="遍历路径数目:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f"{self.way_sum}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.05 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.05 + y0, width=100, height=30) lab1 = tk.Label(frame_right, text="求解花费时间:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f'{self.end - self.start:.4f} s', bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.10 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.10 + y0, width=100, height=30) lab = tk.Label(frame_right, text="自动求解时间最短路径", bg=RED, fg=BLACK, font=('微软雅黑', 20)) lab.place(rely=0.02, width=300, height=30) B = tk.Button(frame_right, text="返回", command=lambda: self.Solve_display()) B.place(relx=0.1, rely=y0, width=50, height=30) lab1 = tk.Label(frame_right, text="时间最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) f = 0 way = '' for a in self.ans: if f == 0: f = 1 else: way += "->" way += d.Nodes[a][1] # way += d.Nodes[0][1] # print(ans, "444", way) # print (ans) lab2 = tk.Label(frame_right, text=f"{way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') tim = 0 cost = 0 for i in range(len(self.ans) - 1): tim += d.Edges[G.node_edge(self.ans[i], self.ans[i + 1])][7] cost += d.Edges[G.node_edge(self.ans[i], self.ans[i + 1])][6] lab1.place(relx=0.1, rely=0.2 + y0, width=100, height=30) lab2.place(relx=0.1, rely=0.25 + y0, width=200, height=100) lab1 = tk.Label(frame_right, text="该路径时间:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f"{tim} min", bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.5 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.5 + y0, width=100, height=30) lab1 = tk.Label(frame_right, text="该路径距离:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f'{cost} km', bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.55 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.55 + y0, width=100, height=30) def auto_lowest_cost_condition(self): # 标记遍历路径(必经) for w in frame_right.winfo_children(): w.destroy() # 清除右侧组件 a = -1 b = -1 for node in d.Nodes: if node[2] == 1: a = node[0] if node[2] == 2: b = node[0] if a == -1 or b == -1: tk.messagebox.askokcancel(title='错误', message='未选择节点') return self.cura = a self.curb = b y0 = 0.1 self.start = time.time() self.lowest_cost_dfs_condition() self.end = time.time() # print(self.ans) laba1 = tk.Label(frame_right, text="起点:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) laba2 = tk.Label(frame_right, text=f"{d.Nodes[self.cura][1]}", bg=BLUE, fg=BLACK, font=('微软雅黑', 8)) laba1.place(relx=0.05, rely=0.02 + y0, width=80, height=30) laba2.place(relx=0.35, rely=0.02 + y0, width=50, height=30) labb1 = tk.Label(frame_right, text="终点:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) labb2 = tk.Label(frame_right, text=f"{d.Nodes[self.curb][1]}", bg=BLUE, fg=BLACK, font=('微软雅黑', 8)) labb1.place(relx=0.52, rely=0.02 + y0, width=80, height=30) labb2.place(relx=0.82, rely=0.02 + y0, width=50, height=30) y0 += 0.1 lab1 = tk.Label(frame_right, text="遍历路径数目:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f"{self.way_sum}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.05 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.05 + y0, width=100, height=30) lab1 = tk.Label(frame_right, text="求解花费时间:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f'{self.end - self.start:.4f} s', bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.10 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.10 + y0, width=100, height=30) lab = tk.Label(frame_right, text="求解最短路径(含必经点)", bg=RED, fg=BLACK, font=('微软雅黑', 18)) lab.place(rely=0.02, width=300, height=30) B = tk.Button(frame_right, text="返回", command=lambda: self.Solve_display()) B.place(relx=0.1, rely=y0, width=50, height=30) lab1 = tk.Label(frame_right, text="距离最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) if not self.check_condition(self.ans): way = '未找到合法路径' else: f = 0 way = '' for a in self.ans: if f == 0: f = 1 else: way += "->" way += d.Nodes[a][1] lab2 = tk.Label(frame_right, text=f"{way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') tim = 0 cost = 0 for i in range(len(self.ans) - 1): tim += d.Edges[G.node_edge(self.ans[i], self.ans[i + 1])][7] cost += d.Edges[G.node_edge(self.ans[i], self.ans[i + 1])][6] lab1.place(relx=0.1, rely=0.2 + y0, width=100, height=30) lab2.place(relx=0.1, rely=0.25 + y0, width=200, height=100) lab1 = tk.Label(frame_right, text="该路径时间:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f"{tim} min", bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.55 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.55 + y0, width=100, height=30) lab1 = tk.Label(frame_right, text="该路径距离:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f'{cost} km', bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.5 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.5 + y0, width=100, height=30) def auto_lowest_cost(self): # 标记遍历路径 for w in frame_right.winfo_children(): w.destroy() # 清除右侧组件 a = -1 b = -1 for node in d.Nodes: if node[2] == 1: a = node[0] if node[2] == 2: b = node[0] if a == -1 or b == -1: tk.messagebox.askokcancel(title='错误', message='未选择节点') return self.cura = a self.curb = b y0 = 0.1 self.start = time.time() self.lowest_cost_dfs() self.end = time.time() # print(self.ans) laba1 = tk.Label(frame_right, text="起点:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) laba2 = tk.Label(frame_right, text=f"{d.Nodes[self.cura][1]}", bg=BLUE, fg=BLACK, font=('微软雅黑', 8)) laba1.place(relx=0.05, rely=0.02 + y0, width=80, height=30) laba2.place(relx=0.35, rely=0.02 + y0, width=50, height=30) labb1 = tk.Label(frame_right, text="终点:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) labb2 = tk.Label(frame_right, text=f"{d.Nodes[self.curb][1]}", bg=BLUE, fg=BLACK, font=('微软雅黑', 8)) labb1.place(relx=0.52, rely=0.02 + y0, width=80, height=30) labb2.place(relx=0.82, rely=0.02 + y0, width=50, height=30) y0 += 0.1 lab1 = tk.Label(frame_right, text="遍历路径数目:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f"{self.way_sum}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.05 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.05 + y0, width=100, height=30) lab1 = tk.Label(frame_right, text="求解花费时间:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f'{self.end - self.start:.4f} s', bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.10 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.10 + y0, width=100, height=30) lab = tk.Label(frame_right, text="自动求解距离最短路径", bg=RED, fg=BLACK, font=('微软雅黑', 20)) lab.place(rely=0.02, width=300, height=30) B = tk.Button(frame_right, text="返回", command=lambda: self.Solve_display()) B.place(relx=0.1, rely=y0, width=50, height=30) lab1 = tk.Label(frame_right, text="距离最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) f = 0 way = '' for a in self.ans: if f == 0: f = 1 else: way += "->" way += d.Nodes[a][1] # way += d.Nodes[0][1] # print(ans, "444", way) # print (ans) lab2 = tk.Label(frame_right, text=f"{way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') tim = 0 cost = 0 for i in range(len(self.ans) - 1): tim += d.Edges[G.node_edge(self.ans[i], self.ans[i + 1])][7] cost += d.Edges[G.node_edge(self.ans[i], self.ans[i + 1])][6] lab1.place(relx=0.1, rely=0.2 + y0, width=100, height=30) lab2.place(relx=0.1, rely=0.25 + y0, width=200, height=100) lab1 = tk.Label(frame_right, text="该路径时间:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f"{tim} min", bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.55 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.55 + y0, width=100, height=30) lab1 = tk.Label(frame_right, text="该路径距离:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f'{cost} km', bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.5 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.5 + y0, width=100, height=30) def dfs_panel_condition(self): # 标记遍历路径(区分必经/非必经) for w in frame_right.winfo_children(): w.destroy() # 清除右侧组件 y0 = 0.1 self.start = time.time() self.node_dfs_condition() self.end = time.time() lab1 = tk.Label(frame_right, text="遍历路径数目:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f"{self.way_sum}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.05 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.05 + y0, width=100, height=30) lab1 = tk.Label(frame_right, text="求解花费时间:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f'{self.end - self.start:.4f} s', bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.10 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.10 + y0, width=100, height=30) lab = tk.Label(frame_right, text="求解路径(区分必经点)", bg=RED, fg=BLACK, font=('微软雅黑', 20)) lab.place(rely=0.02, width=300, height=30) B = tk.Button(frame_right, text="返回", command=lambda: self.Solve_display()) B.place(relx=0.1, rely=y0, width=50, height=30) lab1 = tk.Label(frame_right, text="最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) # 根据遍历结果输出最短路径 way = "" for a in self.ans: way += d.Nodes[a][1] way += "->" way += d.Nodes[0][1] if not self.check_condition(self.ans): way = "未找到联通路径" lab2 = tk.Label(frame_right, text=f"{way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab1.place(relx=0.1, rely=0.2 + y0, width=80, height=30) lab2.place(relx=0.1, rely=0.25 + y0, width=200, height=100) more = 0 way = '' for moreans in self.mutians: more += 1 if more > 1: way += '\n' way += str(more) + ': ' for a in moreans: way += d.Nodes[a][1] way += "->" way += d.Nodes[0][1] if more: lab1 = tk.Label(frame_right, text="其他最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = scrolledtext.ScrolledText(frame_right, width=50, height=5, bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab2.insert('end', way) lab2.configure(state=DISABLED) lab1.place(relx=0.1, rely=0.2 + y0 + 0.2, width=120, height=30) lab2.place(relx=0.1, rely=0.25 + y0 + 0.2, width=240, height=200) def dfs_panel(self): # dfs面板显示 for w in frame_right.winfo_children(): w.destroy()# 清除右侧组件 y0 = 0.1 self.start = time.time()#记录开始时间 self.node_dfs()#执行dfs搜索算法 self.end = time.time()#记录结束时间 lab1 = tk.Label(frame_right, text="遍历路径数目:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f"{self.way_sum}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.05 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.05 + y0, width=100, height=30) lab1 = tk.Label(frame_right, text="求解花费时间:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f'{self.end - self.start:.4f} s', bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.10 + y0, width=100, height=30) lab2.place(relx=0.5, rely=0.10 + y0, width=100, height=30) lab = tk.Label(frame_right, text="自动求解优化路径-遍历", bg=RED, fg=BLACK, font=('微软雅黑', 20)) lab.place(rely=0.02, width=300, height=30) B = tk.Button(frame_right, text="返回", command=lambda: self.Solve_display()) B.place(relx=0.1, rely=y0, width=50, height=30) lab1 = tk.Label(frame_right, text="最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) # 根据遍历结果输出最短路径 way = "" for a in self.ans: way += d.Nodes[a][1] way += "->" way += d.Nodes[0][1] if not len(self.ans) == len(d.Nodes): way = "未找到联通路径" lab2 = tk.Label(frame_right, text=f"{way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab1.place(relx=0.1, rely=0.2 + y0, width=80, height=30) lab2.place(relx=0.1, rely=0.25 + y0, width=200, height=100) # 如果有多条最短路径，则根据遍历结果依次输出 more = 0 way = '' for moreans in self.mutians: more += 1 if more > 1: way += '\n' way += str(more) + ': ' for a in moreans: way += d.Nodes[a][1] way += "->" way += d.Nodes[0][1] if more: lab1 = tk.Label(frame_right, text="其他最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = scrolledtext.ScrolledText(frame_right, width=50, height=5,bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab2.insert('end', way) lab2.configure(state=DISABLED) lab1.place(relx=0.1, rely=0.2 + y0 + 0.2, width=120, height=30) lab2.place(relx=0.1, rely=0.25 + y0 + 0.2, width=240, height=200) def greedy_panel(self): # 标记贪心路径 for w in frame_right.winfo_children(): w.destroy() # 清除右侧组件 lab = tk.Label(frame_right, text="自动求解贪心路径", bg=RED, fg=BLACK, font=('微软雅黑', 20)) lab.place(rely=0.02, width=300, height=30) y0 = 0.1 B = tk.Button(frame_right, text="返回", command=lambda: self.Solve_display()) B.place(relx=0.1, rely=y0, width=50, height=30) lab1 = tk.Label(frame_right, text="贪心法求得路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.2 + y0, width=150, height=30) # 求解贪心路径 self.node_greedy() lab1 = tk.Label(frame_right, text="求解花费时间:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.10 + y0, width=100, height=30) lab2 = tk.Label(frame_right, text=f'{self.end - self.start:.4f} s', bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab2.place(relx=0.5, rely=0.10 + y0, width=100, height=30) # 显示求解获得的贪心路径 way = "" for a in self.ans: way += d.Nodes[a][1] way += "->" way += d.Nodes[0][1] if not len(self.ans) == len(d.Nodes): way = "贪心法无法找到通路" lab2 = tk.Label(frame_right, text=f"{way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab2.place(relx=0.1, rely=0.25 + y0, width=200, height=100) # 显示当前路径消耗的总成本与总时间 dis = 0 tim = 0 for edge in d.Edges: if edge[4] == True: dis += edge[6] tim += edge[7] lab1 = tk.Label(frame_right, text="路径距离/成本:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f'{dis}', bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.40 + y0, width=130, height=30) lab2.place(relx=0.5, rely=0.40 + y0, width=100, height=30) lab1 = tk.Label(frame_right, text="路径时间:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) lab2 = tk.Label(frame_right, text=f'{tim}', bg=BLUE, fg=BLACK, font=('微软雅黑', 12)) lab1.place(relx=0.1, rely=0.45 + y0, width=130, height=30) lab2.place(relx=0.5, rely=0.45 + y0, width=100, height=30) def check_condition(self, ways): con = 0 for w in ways: if d.Nodes[w][4] == 1: con += 1 if con == self.con: return 1 return 0 def dfs_condition(self, i, ways, sum, flag): if self.check_condition(ways) and d.Edges[G.node_edge(i, 0)][8] == 1 and d.Edges[G.node_edge(i, 0)][3] == 1: # 如果遍历的必经节点数目符合要求，则说明这是一条符合要求的路径 self.way_sum += 1#增加一个已搜索路径 sum += d.Edges[G.node_edge(i, 0)][6]#更新路径花费 if sum < self.minn:# 如果该路径的cost小于minn，则更新最短路径 self.ans.clear()#清除原答案 self.mutians.clear()#清除其他答案 self.ans = ways.copy()#将当前路径加入到答案中 self.minn = sum#更新最短路径 elif sum == self.minn:# 如果该路径的cost等于minn，则记录在mutians中 self.mutians.append(ways.copy())#将当前路径加入到其他路径数组中 for j in d.Edges:# 遍历该节点的所有路径，并且对所有可能路径进行尝试 if j[1] == i and flag[j[2]] == 0 and j[8] == 1 and j[3] == 1: ways.append(j[2])# 如果存在一节点还没被访问过，则将其加入搜索队列 flag[j[2]] = 1 self.dfs_condition(j[2], ways, sum + j[6], flag) flag[j[2]] = 0 ways.pop() if j[2] == i and flag[j[1]] == 0 and j[8] == 1 and j[3] == 1: flag[j[1]] = 1 ways.append(j[1]) self.dfs_condition(j[1], ways, sum + j[6], flag) ways.pop() flag[j[1]] = 0 return way_flag = 0#标记问题是否解决 def random_way(self, i, ways, sum, flag): if self.way_flag:#若已找到一条路径，则直接返回 return if len(ways) == len(d.Nodes) and d.Edges[G.node_edge(i, 0)][8] == 1\ and d.Edges[node_edge(i, 0)][3] == 1: # 如果遍历的节点数目符合要求，则说明这是一条符合要求的路径 sum += d.Edges[node_edge(i, 0)][6] # 更新当前路径长度 self.way_flag = 1#将问题标记为已解决 for way in ways: # 输出当前答案 print(way, end=' ') return cur_Edges = d.Edges.copy()# 随机打乱该点能接触到的路径 random.shuffle(cur_Edges) for j in cur_Edges: # 遍历该节点的所有路径，并且对所有可能路径进行尝试 if j[1] == i and flag[j[2]] == 0 and j[8] == 1 and j[3] == 1: # 如果存在一条路径，且对面节点还没被访问过，则将其加入搜索队列 ways.append(j[2])#将该点加入路径 flag[j[2]] = 1#将该点标记为已探索 self.random_way(j[2], ways, sum + j[6], flag)# 递归搜索路径 flag[j[2]] = 0#将该点标记为未探索 ways.pop()#将该点移除路径 if j[2] == i and flag[j[1]] == 0 and j[8] == 1 and j[3] == 1: flag[j[1]] = 1#将该点加入路径 ways.append(j[1])#将该点标记为已探索 self.random_way(j[1], ways, sum + j[6], flag)# 递归搜索路径 ways.pop()#将该点标记为未探索#将该点移除路径 flag[j[1]] = 0#将该点标记为未探索 return def dfs(self, i, ways, sum, flag): if len(ways) == len(d.Nodes) and d.Edges[node_edge(i, 0)][8] == 1\ and d.Edges[node_edge(i, 0)][3] == 1: # 如果遍历的节点数目符合要求，则符合要求 self.way_sum += 1 # 遍历路径的数目加一 sum += d.Edges[node_edge(i, 0)][6] # 更新当前路径长度 if sum < self.minn: # 如果该路径的cost小于minn，则更新最短路径 self.ans.clear() # 清除ans数组 self.mutians.clear() # 清除其他答案数组 self.ans = ways.copy() self.minn = sum # 更新最短路径 elif sum == self.minn: # 如果该路径的cost等于minn，则记录在mutians中 moreans = []#用于记录这条路径node_dfs_condition for way in ways:#将路径途径节点逐个加入 moreans.append(way) self.mutians.append(moreans)# 将该路径加入答案中 cur_Edges = d.Edges.copy()# 随机打乱该点能接触到的路径 random.shuffle(cur_Edges) for j in cur_Edges:# 遍历该节点的所有路径，并且对所有可能路径进行尝试 if j[1] == i and flag[j[2]] == 0 and j[8] == 1 and j[3] == 1: # 如果存在一条路径，且对面节点还没被访问过，则将其加入搜索队列 ways.append(j[2])#将该点加入路径 flag[j[2]] = 1#将该点标记为已探索 self.dfs(j[2], ways, sum + j[6], flag)# 递归搜索路径 flag[j[2]] = 0#将该点标记为未探索 ways.pop()#将该点移除路径 if j[2] == i and flag[j[1]] == 0 and j[8] == 1 and j[3] == 1: flag[j[1]] = 1#将该点加入路径 ways.append(j[1])#将该点标记为已探索 self.dfs(j[1], ways, sum + j[6], flag)# 递归搜索路径 ways.pop()#将该点标记为未探索#将该点移除路径 flag[j[1]] = 0#将该点标记为未探索 return def lcost_dfs_condition(self, i, ways, sum, flag): if i == self.curb:# 若该节点为目标节点 self.way_sum += 1#遍历路径数加一 if self.check_condition(ways):# 若遍历节点数符合要求 if sum < self.minn:#若路径花费更短，则更新答案 self.ans = ways.copy()#更新答案 self.minn = sum#更新最短路径 return for j in d.Edges:#遍历该点能到达的所有节点 if j[1] == i and flag[j[2]] == 0 and j[8] == 1 and j[3] == 1:#若该点未访问，则尝试访问 ways.append(j[2])#将该点加入路径 flag[j[2]] = 1#将该点标记为访问 self.lcost_dfs_condition(j[2], ways, sum + j[6], flag)#递归搜索路径 flag[j[2]] = 0#将该点移除路径 ways.pop()#将该点移除路径 if j[2] == i and flag[j[1]] == 0 and j[8] == 1 and j[3] == 1: flag[j[1]] = 1#将该点标记为访问 ways.append(j[1])#将该点加入路径 self.lcost_dfs_condition(j[1], ways, sum + j[6], flag)#递归搜索路径 ways.pop()#将该点移除路径 flag[j[1]] = 0#将该点标记为未访问 return def lcost_dfs(self, i, ways, sum, flag): # print(i) if i == self.curb: self.way_sum += 1 # print(ways, sum, self.minn) if sum < self.minn: self.ans = ways.copy() self.minn = sum return for j in d.Edges: if j[1] == i and flag[j[2]] == 0 and j[8] == 1 and j[3] == 1: ways.append(j[2]) flag[j[2]] = 1 self.lcost_dfs(j[2], ways, sum + j[6], flag) flag[j[2]] = 0 ways.pop() if j[2] == i and flag[j[1]] == 0 and j[8] == 1 and j[3] == 1: flag[j[1]] = 1 ways.append(j[1]) self.lcost_dfs(j[1], ways, sum + j[6], flag) ways.pop() flag[j[1]] = 0 return def ltime_dfs(self, i, ways, sum, flag): if i == self.curb:#若已经到达目标点，则结束搜索 self.way_sum += 1#遍历路径加一 if sum < self.minn:#若耗时少于最短时间 self.ans = ways.copy()#更新答案 self.minn = sum#更新最短时间 return for j in d.Edges:#遍历当前节点能到达的所有节点 if j[1] == i and flag[j[2]] == 0 and j[8] == 1 and j[3] == 1:#若该节点未遍历则尝试该条路径 ways.append(j[2])#将该节点加入路径 flag[j[2]] = 1#将该节点标记为已经过 self.ltime_dfs(j[2], ways, sum + j[7], flag)#进行递归搜索 flag[j[2]] = 0#将该节点标记为未经过 ways.pop() if j[2] == i and flag[j[1]] == 0 and j[8] == 1 and j[3] == 1: flag[j[1]] = 1#将该节点加入路径 ways.append(j[1])#将该节点标记为已经过 self.ltime_dfs(j[1], ways, sum + j[7], flag)#进行递归搜索 ways.pop()#将该节点移除路径 flag[j[1]] = 0#将该节点标记为未经过 def lowest_cost_dfs_condition(self): # 遍历 # 每两个点之间只保留最短路径 E.edge_del_all(1) self.ans.clear() self.way_sum = 0 self.con = 0 for n in d.Nodes: if n[4]: self.con += 1 for edge in d.Edges: edge[4] = False # for i in range(len(d.Nodes)): i = self.cura self.minn = float("inf") flag = [0] * len(d.Nodes) flag[i] = 1 self.lcost_dfs_condition(i, [i], 0, flag) for way in range(len(self.ans) - 1): d.Edges[G.node_edge(self.ans[way], self.ans[way + 1])][4] = True G.draw() def lowest_cost_dfs(self): # 遍历 # 每两个点之间只保留最短路径 E.edge_del_all(1) # E.newedge_del_all() self.way_sum = 0 self.ans = [] for edge in d.Edges: edge[4] = False # for i in range(len(d.Nodes)): i = self.cura self.minn = float("inf") flag = [0] * len(d.Nodes) flag[i] = 1 self.lcost_dfs(i, [i], 0, flag) for way in range(len(self.ans) - 1): d.Edges[G.node_edge(self.ans[way], self.ans[way + 1])][4] = True G.draw() def lowest_time_dfs(self): # 遍历 self.start = time.time()#记录开始时间 E.edge_del_all(2)#每两条边只保留时间最短路径（剪枝） self.way_sum = 0#初始化路径数目 self.ans = []#清空答案 for edge in d.Edges: edge[4] = False#清空标记 i = self.cura#初始化出发点 self.minn = float("inf")#初始化最短路径为无穷 flag = [0] * len(d.Nodes)#初始化已到达点 flag[i] = 1#将出发点标记为已到达 self.ltime_dfs(i, [i], 0, flag)#深度优先搜索确定答案 for way in range(len(self.ans) - 1):#标记途径路径 d.Edges[G.node_edge(self.ans[way], self.ans[way + 1])][4] = True self.end = time.time()#记录结束时间 G.draw()#重新绘图 def node_dfs_condition(self):# 遍历 E.edge_del_all(1)# 每两个节点之间只保留距离最短的一条 self.con = 0#初始化经过的必经点数目 self.way_sum = 0# 初始化遍历的节点数目 self.ans.clear()#清除答案数组 for node in d.Nodes:#计算必经点数量 if node[4] == 1: self.con += 1 for edge in d.Edges:#清空标记 edge[4] = False i = 0 self.minn = float("inf")#初始化最短路径为无穷 flag = [0] * len(d.Nodes)#初始化已经过数组 flag[i] = 1#将初始点标记为已经过 self.dfs_condition(i, [0], 0, flag)#开始遍历搜索合法路径 if not self.check_condition(self.ans):#若没找到合法路径在进行报告 tk.messagebox.askokcancel(title='结果', message='未找到联通路径') G.draw() return for way in range(len(self.ans) - 1):#逐个标记答案路径 d.Edges[G.node_edge(self.ans[way], self.ans[way + 1])][4] = True last = self.ans.pop()#弹出最后一个点 d.Edges[G.node_edge(last, i)][4] = True#链接首位形成环线 self.ans.append(last)#重新加入该点 G.draw()#绘图 def node_dfs(self): # 遍历 self.start = time.time() # 记录开始时间 E.edge_del_all(1)# 每两个节点之间只保留距离最短的一条 self.way_sum = 0# 初始化遍历的节点数目 for edge in d.Edges:#清空标记 edge[4] = False i = 0#起始点 self.minn = float("inf")#初始化最小值为正无穷 flag = [0] * len(d.Nodes)#初始化已经过点 flag[i] = 1#将起点标记为已经过 self.dfs(i, [0], 0, flag)#使用dfs算法搜索路径 if not len(self.ans) == len(d.Nodes):#若找不到符合要求的路径，则输出信息 tk.messagebox.askokcancel(title='结果', message='未找到联通路径') G.draw() return for way in range(len(self.ans) - 1):#标记一条路径 d.Edges[G.node_edge(self.ans[way], self.ans[way + 1])][4] = True last = self.ans.pop()#取出最后一个点 d.Edges[G.node_edge(last, i)][4] = True#将起始点与最终点链接形成环线 self.ans.append(last)#将最终点加回ans中 self.end = time.time() # 记录结束时间 G.draw() def node_greedy(self): # 贪心 self.start = time.time()#记录开始时间 self.ans.clear()#初始化答案列表 E.edge_del_all(1)# 两点间仅保留距离最短路径 for edge in d.Edges:#清空标记 edge[4] = False i = 0 # 起始点 ways = [i] flag = [0] * len(d.Nodes) # 初始化已经过点 cur = i#初始化起始点 sum = 0#初始化路径长度 flag[cur] = 1#将起始点标记为已经过 nxt = cur for ii in range(len(d.Nodes)): minn = float("inf")# 初始化最小值 for j in d.Edges:# 每一步选择当前最短的链接加到路径中去 if j[1] == cur and flag[j[2]] == 0 and j[6] < minn and j[8] == 1 and j[3] == 1: nxt = j[2] minn = j[6] if j[2] == cur and flag[j[1]] == 0 and j[6] < minn and j[8] == 1 and j[3] == 1: nxt = j[1] minn = j[6] if nxt != cur:#只要找到了新的路径，则加入路径中 ways.append(nxt) flag[nxt] = 1 sum += minn cur = nxt self.ans = ways.copy() # 如果找到的路径不合法，则表示贪心法无法求解得到合法路径 if (not len(self.ans) == len(d.Nodes)) or (d.Edges[G.node_edge(0, ways[len(ways) - 1])][3] == 0): tk.messagebox.askokcancel(title='结果', message='贪心法无法找到合法路径') self.ans.clear() return -1 for way in range(len(ways) - 1):#标记一条路径 d.Edges[G.node_edge(ways[way], ways[way + 1])][4] = True d.Edges[G.node_edge(ways[len(ways) - 1], i)][4] = True#标记起点终点形成环线 self.end = time.time()#记录结束时间 G.draw() # root.update() def check(self): # 检查是否存在最短路 find = [] for i in range(len(d.Nodes)): find.append(i) for edge in d.Edges: if edge[8] == 1 and edge[3] == 0: continue x = edge[1] y = edge[2] while not x == find[x]: x = find[x] while not y == find[y]: y = find[y] if x < y: find[y] = x else: find[x] = y flag = 1 for i in range(len(d.Nodes)): if not find[i] == find[0]: flag = 0 if flag: tk.messagebox.askokcancel(title='结果', message='该图存在最短路') else: tk.messagebox.askokcancel(title='结果', message='该图不能完全互通') if __name__ == '__main__': G.draw() solve = Solve() solve.Solve_display() mainloop()