Грокаем алгоритмы

В предыдущей главе все соседи узла были сохранены в хеш-таблице:

graph["you"] = ["alice", "bob", "claire"]

Но на этот раз необходимо сохранить как соседей, так и стоимость перехода к соседу. Предположим, у начального узла есть два соседа, A и B.

Как представить веса этих ребер? Почему бы не воспользоваться другой хеш-таблицей?

graph["start"] = {}

graph["start"]["a"] = 6

graph["start"]["b"] = 2

Итак, graph["start"] является хеш-таблицей. Для получения всех соседей начального узла можно воспользоваться следующим выражением:

>>> print graph["start"].keys()

["a", "b"]

Одно ребро ведет из начального узла в A, а другое — из начального узла в B. А если вы захотите узнать веса этих ребер?

>>> print graph["start"]["a"]

2

>>> print graph["start"]["b"]

6

Включим в граф остальные узлы и их соседей:

graph["a"] = {}

graph["a"]["fin"] = 1

graph["b"] = {}

graph["b"]["a"] = 3

graph["b"]["fin"] = 5

graph["fin"] = {}  У конечного узла нет соседей

Полная хеш-таблица графа выглядит так:

Также понадобится хеш-таблица для хранения стоимостей всех узлов.

Стоимость узла определяет, сколько времени потребуется для перехода к этому узлу от начального узла. Вы знаете, что переход от начального узла к узлу B занимает 2 минуты. Вы знаете, что для перехода к узлу A требуется 6 минут (хотя, возможно, вы найдете более быстрый путь). Вы не знаете, сколько времени потребуется для достижения конечного узла. Если стоимость еще неизвестна, она считается бесконечной. Можно ли представить бесконечность в Python? Оказывается, можно:

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]