Теперь найдем узел с наименьшей стоимостью и обновим стоимости его соседей. В этом случае постер оказывается узлом с наименьшей стоимостью. Итак, в соответствии с алгоритмом Дейкстры, к постеру невозможно перейти более дешевым способом, чем с оплатой $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! Код функции будет приведен далее, а пока рассмотрим пример использования алгоритма в действии.
Найти узел с наименьшей стоимостью.
Получить стоимость и соседей этого узла.
