Нахождение ближайшей остановки из массива с помощью Алгоритма Дейкстры

Пользователь

tysrusko

от tysrusko , в категории: Python , 7 месяцев назад

Имеется следующий код:

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

Весь этот код это реализация алгоритма Дейкстры для нахождения кратчайших маршрутов между остановками. Он сделан таким образом, чтобы в массив array заносился пул остановок, и до каждой из них будет рассчитываться кратчайшее расстояние, а также будут выводится остановки которые лежат на пути к ним.

Собственно в чем стоит вопрос.

Необходимо переделать функцию run_dijkstra таким образом, чтобы остановки из массива array выводились не по очереди как их занесли, а исходя из того, какая остановка стоит ближе к стартовой точке.

Как я примерно это вижу, функция run_dijkstra полностью прогоняет массив array, находит расстояние от стартовой точки до каждой точки из массива и выбирает кратчайшее, после чего эта выбранная точка становится стартовой, она из массива убирается, и массив прогоняется заново и так до тех пор пока не кончится массив.

Мне нужна помощь с тем как это можно реализовать. Если у вас есть идеи как это можно сделать лучше, с радостью их прочту.

1 | 0

2 ответа

Пользователь

jaren

от jaren , 7 месяцев назад

@tysrusko Попробуйте вот так:

def run_dijkstra():
    global selected_value
    global selected_value1
    global selected_value2
    route = []
    
    while array:
        min_distance = float('inf')
        closest_stop = None
        
        for stop in array:
            graph = Graph(nodes, init_graph)
            previous_nodes, shortest_path = dijkstra_algorithm(graph=graph, start_node=selected_value)
            distance = shortest_path[stop]
            
            # Если найдено более короткое расстояние, обновляем ближайшую остановку
            if distance < min_distance:
                min_distance = distance
                closest_stop = stop
        
        route.append(closest_stop)
        array.remove(closest_stop)
        
        # Обновляем стартовую точку для следующего шага
        selected_value = closest_stop
    
    print(route)

2 | 0

Пользователь

tysrusko

от tysrusko , 7 месяцев назад

Благодарю, в консоли оно действительно в виде массива выводит как надо, но нельзя ли сделать так, чтобы оно выводилось в текстовое поле таким образом, как у меня в коде, то есть используя функцию print_result, которая выводит результат в следующем виде:

Найден следующий лучший маршрут с расстоянием 46.49 км

Склад -> Некрасовская -> 3-я Рабочая -> ТГМУ

Найден следующий лучший маршрут с расстоянием 6.11 км

ТГМУ -> ВВГУ

Найден следующий лучший маршрут с расстоянием 22.78 км

ВВГУ -> 3-я Рабочая -> ДВФУ @jaren

0 | 0

Нахождение ближайшей остановки из массива с помощью Алгоритма Дейкстры

2 ответа

Похожие обсуждения: