Page 171 - Bkhargava_-_Grokaem_algoritmy

170 Глава 7. Алгоритм Дейкстры

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

nм-
стинк~ 5
ПОСТЕР -2

БАР~Б~Н 35

итоrовыЕ.
стоимости

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

Реализация

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

www.trk.kg