infinity = float("inf")
Код создания таблицы стоимостей costs:
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
Для родителей также создается отдельная таблица:
Код создания хеш-таблицы родителей:
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
Наконец, вам нужен массив для отслеживания всех уже обработанных узлов, так как один узел не должен обрабатываться многократно:
processed = []
На этом подготовка завершается. Теперь обратимся к алгоритму.
Сначала я приведу код, а потом мы разберем его более подробно.
node = find_lowest_cost_node(costs) 
Найти узел с наименьшей стоимостью среди необработанных
while node is not None: Если обработаны все узлы, цикл while завершен
cost = costs[node]
neighbors = graph[node]
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 = find_lowest_cost_node(costs) Найти следующий узел для обработки и повторить цикл
Так выглядит алгоритм Дейкстры на языке Python! Код функции будет приведен далее, а пока рассмотрим пример использования алгоритма в действии.
Найти узел с наименьшей стоимостью.
Получить стоимость и соседей этого узла.
Перебрать соседей.
У каждого узла имеется стоимость, которая определяет, сколько времени потребуется для достижения этого узла от начала. Здесь мы вычисляем, сколько времени потребуется для достижения узла A по пути Начало > Узел B > Узел A (вместо Начало > Узел A).
Сравним эти стоимости.
Мы нашли более короткий путь к узлу A! Обновим стоимость.
Новый путь проходит через узел B, поэтому B назначается новым родителем.
Мы снова вернулись к началу цикла. Следующим соседом в цикле for является конечный узел.
Сколько времени потребуется для достижения конечного узла, если идти через узел B?
Потребуется 7 минут. Предыдущая стоимость была бесконечной, а 7 минут определенно меньше бесконечности.
Конечному узлу назначается новая стоимость и новый родитель.
Порядок, мы обновили стоимости всех соседей узла B. Узел помечается как обработанный.
Найти следующий узел для обработки.
Получить стоимость и соседей узла A.
У узла A всего один сосед: конечный узел.
Время достижения конечного узла составляет 7 минут. Сколько времени потребуется для достижения конечного узла, если идти через узел A?
Через узел A можно добраться быстрее! Обновим стоимость и родителя.
После того как все узлы будут обработаны, алгоритм завершается. Надеюсь, этот пошаговый разбор помог вам чуть лучше понять алгоритм. С функцией find_lowest_cost_node узел с наименьшей стоимостью находится проще простого. Код выглядит так:
def ind_lowest_cost_node(costs):
lowest_cost = loat("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
Упражнения
7.1 Каков вес кратчайшего пути от начала до конца в каждом из следующих графов?