Page 159 - Bkhargava_-_Grokaem_algoritmy

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

Для вычисления кратчайшего пути в невзвешенном графе используется
поиск в ширину. Кратчайшие пути во взвешенном графе вычисляются по
алгоритму Дейкстры . В графах также могут присутствовать циклы:

!!МКЛ\ nтть.
НАЧМНАЮ\4ИР!СJI
С У.ЗЛА@,
мо~ЕТ &E.PHYТb­
CJI К У.ЗЛУ@

Это означает, что вы можете начать с некоторого узла, перемещаться по
графу, а потом снова оказаться в том же узле. Предположим, вы ищете
кратчайший путь в графе, содержащем цикл.

~АЧАЛО KOHEU

Есть ли смысл в перемещении по циклу? Что ж, вы можете использовать
путь без прохождения цикла:

А можете пройти по циклу:

ОБ14МР!
&Е.С:
13

www.trk.kg