Ребро, ведущее от пластинки к постеру, имеет отрицательный вес! Если Рама пойдет на этот обмен, он получит $7. Теперь к постеру можно добраться двумя способами.
А значит, во втором обмене появляется смысл — Рама получает $2!
Теперь, если вы помните, Рама может обменять постер на барабан. И здесь возможны два пути.
Второй путь обойдется на $2 дешевле, поэтому нужно выбрать этот путь, верно?
И знаете что? Если применить алгоритм Дейкстры к этому графу, Рама выберет неверный путь. Он пойдет по более длинному пути. Алгоритм Дейкстры не может использоваться при наличии ребер, имеющих отрицательный вес. Такие ребра нарушают работу алгоритма. Посмотрим, что произойдет, если попытаться применить алгоритм Дейкстры к этому графу. Все начинается с построения таблицы стоимостей.
Теперь найдем узел с наименьшей стоимостью и обновим стоимости его соседей. В этом случае постер оказывается узлом с наименьшей стоимостью. Итак, в соответствии с алгоритмом Дейкстры, к постеру невозможно перейти более дешевым способом, чем с оплатой $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? Оказывается, можно: