Граф:
from math import inf
def function_node(costs):
lowest_cost = inf
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost < lowest_cost and node not in processed: # обязательно берём минимальную цену, т.к. неизвестная цена всегда бесконечность
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node # функция вернёт узел с минимальной ценой из ХЕШ-ТАБЛИЦЫ ДЛЯ ХРАНЕНИЯ СТОИМОСТИ ВСЕХ УЗЛОВ
#############################################################################
#############################################################################
"""СОЗДАНИЕ ГРАФА С ИСПОЛЬЗОВАНИЕМ ХЕШ-ТАБЛИЦЫ. ВХОДНЫЕ ДАННЫЕ."""
graph = {} # словарь соседей со стоимостями перехода ---> {'Начало': {'а': 6, 'в': 2}, 'а': {'Конец': 1}, 'в': {'а': 3, 'Конец': 5}, 'Конец': {}}
# начало
graph["Начало"] = {}
graph["Начало"]["а"] = 6
graph["Начало"]["в"] = 2
# а
graph["а"] = {}
graph["а"]["Конец"] = 1
# в
graph["в"] = {}
graph["в"]["а"] = 3
graph["в"]["Конец"] = 5
# Конец
graph["Конец"] = {} # у конечного узла нет соседей
#############################################################################
#############################################################################
"""ХЕШ-ТАБЛИЦА ДЛЯ ХРАНЕНИЯ СТОИМОСТИ ВСЕХ УЗЛОВ. ЗАПОЛНЯЕТСЯ В ПРОЦЕССЕ."""
costs = {} # ---> {'а': 6, 'в': 2, 'Конец': inf}
costs["а"] = 6
costs["в"] = 2
costs["Конец"] = inf # пока это бесконечность
#############################################################################
#############################################################################
"""ХЕШ-ТАБЛИЦА ДЛЯ РОДИТЕЛЕЙ. ЗАПОЛНЯЕТСЯ В ПРОЦЕССЕ."""
parents = {} # ---> {'а': 'Начало', 'в': 'Начало', 'Конец': None}
parents["а"] = "Начало"
parents["в"] = "Начало"
parents["Конец"] = None
#############################################################################
#############################################################################
"""СПИСОК ДЛЯ ОТСЛЕЖИВАНИЯ ВСЕХ УЖЕ ОБРАБОТАННЫХ УЗЛОВ. НУЖЕН ДЛЯ ИЗБЕЖАНИЯ ЦИКЛОВ."""
processed = []
node = function_node(costs) # найдём узел с наименьшей стоимостью из уже известных и необработанных ---> к примеру: в
while node is not None: # цикл завершится, если обработаны все узлы
cost = costs[node] # ---> int; цена для узла, он же узел с наименьшей стоимостью
neighbors = graph[node] # ---> 'в': {'а': 3, 'Конец': 5}; соседи узла
for n in neighbors.keys(): # переберём всех соседей текущего узла
new_cost = cost + neighbors[n] # цена для соседа текущего узла
if costs[n] > new_cost: # проверка цены в хеш-таблице
costs[n] = new_cost # обновим, если новая цена меньше той, что в хеш-таблице
parents[n] = node # обновим родителя, если новая цена меньше той, что в хеш-таблице
processed.append(node) # помещаем узел в список обработанных узлов
node = function_node(costs) # найдём узел с наименьшей стоимостью из уже известных и необработанных
print()
print("Словарь с наименьшими ценами для узлов", costs)
print()
print("Словарь с родителями для узлов", parents)
print()