Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава Страница 27

Теперь найдем узел с наименьшей стоимостью и обновим стоимости его соседей. В этом случае постер оказывается узлом с наименьшей стоимостью. Итак, в соответствии с алгоритмом Дейкстры, к постеру невозможно перейти более дешевым способом, чем с оплатой $0 (а вы знаете, что это неверно!) Как бы то ни было, обновим стоимости его соседей.

Получается, что теперь стоимость барабана составляет $35.

Перейдем к следующему по стоимости узлу, который еще не был обработан.

Обновим стоимости его соседей.

Узел «постер» уже был обработан, однако вы обновляете его стоимость. Это очень тревожный признак — обработка узла означает, что к нему невозможно добраться с меньшими затратами. Но вы только что нашли более дешевый путь к постеру! У барабана соседей нет, поэтому работа алгоритма завершена. Ниже приведены итоговые стоимости.

Чтобы добраться до барабанов, Раме потребовалось $35. Вы знаете, что существует путь, который стоит всего $33, но алгоритм Дейкстры его не находит. Алгоритм Дейкстры предположил, что, поскольку вы обрабатываете узел «постер», к этому узлу невозможно добраться быстрее. Это предположение работает только в том случае, если ребер с отрицательным весом не существует. Следовательно, использование алгоритма Дейкстры с графом, содержащим ребра с отрицательным весом, невозможно. Если вы хотите найти кратчайший путь в графе, содержащем ребра с отрицательным весом, для этого существует специальный алгоритм, называемый алгоритмом Беллмана—Форда. Рассмотрение этого алгоритма выходит за рамки этой книги, но вы сможете найти хорошие описания в Интернете.

Реализация

Посмотрим, как алгоритм Дейкстры реализуется в программном коде. Ниже изображен граф, который будет использоваться в этом примере.

Для реализации этого примера понадобятся три хеш-таблицы.

Хеш-таблицы стоимостей и родителей будут обновляться по ходу работы алгоритма. Сначала необходимо реализовать граф. Как и в главе 6, для этого будет использована хеш-таблица:

graph = {}

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

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! Код функции будет приведен далее, а пока рассмотрим пример использования алгоритма в действии.

Найти узел с наименьшей стоимостью.

Получить стоимость и соседей этого узла.