May-10-2024, 11:49 AM
current_time = datetime.datetime.now().time()
class Graph(object):
def __init__(self, nodes, init_graph):
self.nodes = nodes
self.graph = self.construct_graph(nodes, init_graph)
def construct_graph(self, nodes, init_graph):
'''
Этот метод обеспечивает симметричность графика. Другими словами, если существует путь от узла A к B со значением V, должен быть путь от узла B к узлу A со значением V.
'''
graph = {}
for node in nodes:
graph[node] = {}
graph.update(init_graph)
for node, edges in graph.items():
for adjacent_node, value in edges.items():
if graph[adjacent_node].get(node, False) == False:
graph[adjacent_node][node] = value
return graph
def get_nodes(self):
"Возвращает узлы графа"
return self.nodes
def get_outgoing_edges(self, node):
"Возвращает соседей узла"
connections = []
for out_node in self.nodes:
if self.graph[node].get(out_node, False) != False:
connections.append(out_node)
return connections
def value(self, node1, node2):
"Возвращает значение ребра между двумя узлами."
return self.graph[node1][node2]
def dijkstra_algorithm(graph, start_node):
unvisited_nodes = list(graph.get_nodes())
# Мы будем использовать этот словарь, чтобы сэкономить на посещении каждого узла и обновлять его по мере продвижения по графику
shortest_path = {}
# Мы будем использовать этот dict, чтобы сохранить кратчайший известный путь к найденному узлу
previous_nodes = {}
# Мы будем использовать max_value для инициализации значения "бесконечности" непосещенных узлов
max_value = sys.maxsize
for node in unvisited_nodes:
shortest_path[node] = max_value
# Однако мы инициализируем значение начального узла 0
shortest_path[start_node] = 0
# Алгоритм выполняется до тех пор, пока мы не посетим все узлы
while unvisited_nodes:
# Приведенный ниже блок кода находит узел с наименьшей оценкой
current_min_node = None
for node in unvisited_nodes: # Iterate over the nodes
if current_min_node == None:
current_min_node = node
elif shortest_path[node] < shortest_path[current_min_node]:
current_min_node = node
# Приведенный ниже блок кода извлекает соседей текущего узла и обновляет их расстояния
neighbors = graph.get_outgoing_edges(current_min_node)
for neighbor in neighbors:
tentative_value = shortest_path[current_min_node] + graph.value(current_min_node, neighbor)
if tentative_value < shortest_path[neighbor]:
shortest_path[neighbor] = tentative_value
# We also update the best path to the current node
previous_nodes[neighbor] = current_min_node
# После посещения его соседей мы отмечаем узел как "посещенный"
unvisited_nodes.remove(current_min_node)
return previous_nodes, shortest_path
def print_result(previous_nodes, shortest_path, start_node, target_node):
path = []
node = target_node
while node != start_node:
path.append(node)
node = previous_nodes[node]
# Добавить начальный узел вручную
path.append(start_node)
result_text = "Найден следующий лучший маршрут с расстоянием {} км".format(shortest_path[target_node])
result_text += "\n" + " -> ".join(reversed(path))
# Вставить результат в текстовое поле
text_input.insert(END, result_text + "\n")
nodes = {"Склад": (43.356374, 132.072318), "Некрасовская": (43.128128, 131.910649), "3-я Рабочая": (43.123089, 131.924877),
"Центр": (43.115797, 131.885064), "Луговая": (43.128078, 131.940321), "Нивельского": (43.112586, 131.943152), "Нейбута": (43.116441, 131.955245), "ДВФУ": (43.025101, 131.894189)}
valuegor = list(nodes.keys())
etaj = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
#Координаты остановок
storage = (43.356374, 132.072318)
necra = (43.128128, 131.910649)
raboch = (43.123089, 131.924877)
center = (43.115797, 131.885064)
lugovaya = (43.128078, 131.940321)
nivels = (43.112586, 131.943152)
newboot = (43.116441, 131.955245)
DVFU = (43.025101, 131.894189)
init_graph = {}
for node in nodes:
init_graph[node] = {}
if current_time < datetime.time(12, 0, 0):
init_graph["Склад"]["Некрасовская"] = round(GD(nodes["Склад"], nodes["Некрасовская"]).km + 5, 2)
init_graph["Склад"]["Центр"] = round(GD(nodes["Склад"], nodes["Центр"]).km + 5, 2)
init_graph["Некрасовская"]["Нивельского"] = round(GD(nodes["Некрасовская"], nodes["Нивельского"]).km + 5, 2)
init_graph["Некрасовская"]["3-я Рабочая"] = round(GD(nodes["Некрасовская"], nodes["3-я Рабочая"]).km + 5, 2)
init_graph["3-я Рабочая"]["Нейбута"] = round(GD(nodes["3-я Рабочая"], nodes["Нейбута"]).km + 5, 2)
init_graph["3-я Рабочая"]["ДВФУ"] = round(GD(nodes["3-я Рабочая"], nodes["ДВФУ"]).km + 5, 2)
init_graph["3-я Рабочая"]["Луговая"] = round(GD(nodes["3-я Рабочая"], nodes["Луговая"]).km + 5, 2)
init_graph["ДВФУ"]["Нейбута"] = round(GD(nodes["ДВФУ"], nodes["Нейбута"]).km + 5, 2)
init_graph["Луговая"]["Нивельского"] = round(GD(nodes["Луговая"], nodes["Нивельского"]).km + 5, 2)
init_graph["Луговая"]["ДВФУ"] = round(GD(nodes["Луговая"], nodes["ДВФУ"]).km + 5, 2)
elif current_time < datetime.time(18, 0, 0):
init_graph["Склад"]["Некрасовская"] = round(GD(nodes["Склад"], nodes["Некрасовская"]).km + 6, 2)
init_graph["Склад"]["Центр"] = round(GD(nodes["Склад"], nodes["Центр"]).km + 5, 2)
init_graph["Некрасовская"]["Нивельского"] = round(GD(nodes["Некрасовская"], nodes["Нивельского"]).km + 6, 2)
init_graph["Некрасовская"]["3-я Рабочая"] = round(GD(nodes["Некрасовская"], nodes["3-я Рабочая"]).km + 6, 2)
init_graph["3-я Рабочая"]["Нейбута"] = round(GD(nodes["3-я Рабочая"], nodes["Нейбута"]).km + 6, 2)
init_graph["3-я Рабочая"]["ДВФУ"] = round(GD(nodes["3-я Рабочая"], nodes["ДВФУ"]).km + 6, 2)
init_graph["3-я Рабочая"]["Луговая"] = round(GD(nodes["3-я Рабочая"], nodes["Луговая"]).km + 6, 2)
init_graph["ДВФУ"]["Нейбута"] = round(GD(nodes["ДВФУ"], nodes["Нейбута"]).km + 6, 2)
init_graph["Луговая"]["Нивельского"] = round(GD(nodes["Луговая"], nodes["Нивельского"]).km + 6, 2)
init_graph["Луговая"]["ДВФУ"] = round(GD(nodes["Луговая"], nodes["ДВФУ"]).km + 6, 2)
else:
init_graph["Склад"]["Некрасовская"] = round(GD(nodes["Склад"], nodes["Некрасовская"]).km + 5, 2)
init_graph["Склад"]["Центр"] = round(GD(nodes["Склад"], nodes["Центр"]).km + 5, 2)
init_graph["Некрасовская"]["Нивельского"] = round(GD(nodes["Некрасовская"], nodes["Нивельского"]).km, 2)
init_graph["Некрасовская"]["3-я Рабочая"] = round(GD(nodes["Некрасовская"], nodes["3-я Рабочая"]).km, 2)
init_graph["3-я Рабочая"]["Нейбута"] = round(GD(nodes["3-я Рабочая"], nodes["Нейбута"]).km, 2)
init_graph["3-я Рабочая"]["ДВФУ"] = round(GD(nodes["3-я Рабочая"], nodes["ДВФУ"]).km, 2)
init_graph["3-я Рабочая"]["Луговая"] = round(GD(nodes["3-я Рабочая"], nodes["Луговая"]).km, 2)
init_graph["ДВФУ"]["Нейбута"] = round(GD(nodes["ДВФУ"], nodes["Нейбута"]).km, 2)
init_graph["Луговая"]["Нивельского"] = round(GD(nodes["Луговая"], nodes["Нивельского"]).km, 2)
init_graph["Луговая"]["ДВФУ"] = round(GD(nodes["Луговая"], nodes["ДВФУ"]).km, 2)
#КОД МЕНЮ
def close_window():
root.destroy()
def save_to_file():
text_to_save = text_input.get("1.0", END)
file_path = filedialog.asksaveasfilename(defaultextension=".txt", filetypes=[("Text files", "*.txt")])
if file_path:
try:
with open(file_path, 'w', encoding='utf-8') as file:
file.write(text_to_save)
except Exception as e:
print(f"An error occurred while saving the file: {e}")
def open_file():
file_path = filedialog.askopenfilename(filetypes=[("Text files", "*.txt")])
if file_path:
try:
with open(file_path, 'r', encoding='utf-8') as file:
text = file.read()
text_input.delete(1.0, END)
text_input.insert(END, text)
except Exception as e:
print(f"An error occurred while opening the file: {e}")
def change_button_color():
color = colorchooser.askcolor(title="Choose Button Color")
if color[1]: # Check if a color was chosen
save_button.config(bg=color[1])
open_button.config(bg=color[1])
exit_button.config(bg=color[1])
slovo_button.config(bg=color[1])
delete_button.config(bg=color[1])
run_button.config(bg=color[1])
def change_menu_color():
color = colorchooser.askcolor(title="Choose Button Color")
if color[1]: # Check if a color was chosen
text_input.config(bg=color[1])
text1_input.config(bg=color[1])
root.config(bg=color[1])
def current_time():
t = time.localtime()
current_time = time.strftime("%H:%M:%S", t)
text1_input.delete(1.0, END)
text1_input.insert(END, current_time)
#Выбор пункта доставки
selected_value = None
def select_value():
global selected_value
selected_value = combo.get()
print(f"Выбрано значение: {selected_value}")
#Выбор этажа
selected_value1 = None
def select_value1():
global selected_value1
selected_index = combo1.current()
selected_value1 = etaj[selected_index]
print("Selected value:", selected_value1)
#Выбор стартовой точки
selected_value2 = None
def select_value2():
global selected_value2
selected_value2 = combo2.get()
print(f"Выбрано значение: {selected_value2}")
def clear_text():
text_input.delete(1.0, END)
text1_input.delete(1.0, END)
root = Tk()
root.title("Меню")
root.geometry("1920x1080")
root.option_add("*tearOff", False)
main_menu = Menu()
file_menu = Menu()
setting_menu = Menu()
selected_font = tk.StringVar(root)
main_menu.add_cascade(label="Файл", menu=file_menu)
main_menu.add_cascade(label="Настройки", menu=setting_menu)
file_menu.add_command(label="Выход", command=close_window)
setting_menu.add_command(label="Выбор цвета кнопок", command = change_button_color)
setting_menu.add_command(label="Выбор цвета меню", command = change_menu_color)
root.config(menu=main_menu)
text_input = Text(root, wrap="word", height=30, width=120, font = ("Arial", 16)) # Указываем высоту и ширину текстового поля
text_input.grid(row=0, column=0, rowspan=3, padx=10, pady=10)
#Подпись для обозначения цены
label = Label(root, text="Стоимость доставки", font = ("Arial", 16))
label.place(x = 340, y = 777)
text1_input = Text(root, wrap="word", height=1, width=25 , font = ("Arial", 16))
text1_input.grid(row=4, column=0, rowspan=1, padx=0, pady=0)
#ввод этажа для доставки
label1 = Label(root, text="Этаж доставки", font = ("Arial", 16))
label1.place(x = 340, y = 807)
#Выбор этажа
combo1 = ttk.Combobox(root, values=etaj)
combo1['values'] = etaj
combo1.grid(row=5, column=0, padx=0, pady=0)
#кнопка Выбора этажа
button_etaj = Button(root, text="Выбрать этаж", command=select_value1)
button_etaj.place(x = 840, y = 807)
save_button = Button(root, text="Сохранить", command=save_to_file)
save_button.grid(row=0, column=1, padx=10, pady=5)
open_button = Button(root, text="Загрузить", command=open_file)
open_button.grid(row=1, column=1, padx=10, pady=5)
#Кнопка выхода
exit_button = Button(root, text="Выход", command=close_window)
exit_button.grid(row=6, column=0, padx=10, pady=5)
#Выбор пункта доставки
combo = ttk.Combobox(root, values=valuegor)
combo.grid(row=2, column=2, padx=10, pady=5)
combo.bind("<<ComboboxSelected>>", select_value)
#Выбор стартовой точки
#combo2 = ttk.Combobox(root, values=nodes)
#combo2.grid(row=3, column=2, padx=10, pady=5)
#combo2.bind("<<Combobox2Selected>>", select_value2)
slovo_button = Button(root, text="Выбрать", command=select_value)
slovo_button.grid(row=2, column=1, padx=10, pady=5)
#slovo1_button = Button(root, text="Выбрать", command=select_value2)
#slovo1_button.grid(row=3, column=1, padx=10, pady=5)
delete_button = Button(root, text="Очистить", command=clear_text)
delete_button.grid(row=4, column=1, padx=10, pady=5)
#Сбор остановок в массив
array = []
def add_value():
value = combo.get()
array.append(value)
#text_input.delete(0, tk.END)
def display_array():
text_input.config(state=tk.NORMAL)
#text_input.delete(1.0, tk.END)
text_input.insert(tk.END, "Текущий список остановок: ")
text_input.insert(tk.END, ', '.join(array))
#text_input.config(state=tk.DISABLED)
add_button = tk.Button(root, text="Добавить значение", command=add_value)
add_button.grid(row=0, column=2)
display_button = tk.Button(root, text="показать массив", command=display_array)
display_button.grid(row=0, column=3)
#Конец этой части кода
#Функция запуска алгоритма Дейкстры
def run_dijkstra():
global selected_value
global selected_value1
global selected_value2
route_value = 0
if selected_value:
for index, znach in enumerate(array):
previous_index = index -1
if index == 0:
graph = Graph(nodes, init_graph)
previous_nodes, shortest_path = dijkstra_algorithm(graph=graph, start_node= selected_value)
print_result(previous_nodes, shortest_path, start_node= selected_value, target_node=znach)
route_value += shortest_path[znach]
elif index < len(array):
previous_znach = array[previous_index]
graph = Graph(nodes, init_graph)
previous_nodes, shortest_path = dijkstra_algorithm(graph=graph, start_node= previous_znach)
print_result(previous_nodes, shortest_path, start_node= previous_znach, target_node=znach)
route_value += shortest_path[znach]
#Рассчет стоимости
traffic_value = 150
if route_value > 30:
traffic_value = 150 * route_value * selected_value1
text1_input.insert(END, traffic_value)
else:
text1_input.insert(END, traffic_value + 150)
text_input.insert(END, route_value)
#text_input.insert(END, result_text)
#Конец рассчета стоимости
# Создайте новую кнопку для запуска алгоритма Дейкстры
run_button = Button(root, text="Запустить Дейкстру", command=run_dijkstra)
run_button.grid(row=4, column=2, padx=10, pady=5)
root.mainloop()All this code is an implementation of Dijkstra's algorithm for finding the shortest routes between stops. It is made in such a way that a pool of stops is entered into the array, and the shortest distance to each of them will be calculated, and the stops that lie on the way to them will be displayed.Actually that is the question.
It is necessary to remake the run_dijkstra function in such a way that stops from the array are displayed not in order as they were entered, but based on which stop is closest to the starting point.
As I roughly see it, the run_dijkstra function completely runs the array array, finds the distance from the starting point to each point from the array and selects the shortest one, after which this selected point becomes the starting point, it is removed from the array, and the array is run again and so on until the array will not end.
I need help with how this can be implemented. If you have ideas on how this can be done better, I would be happy to read them.
переделка под словарь.zip (Size: 5.7 KB / Downloads: 108)