|
|
# -*- 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() |
