Page 160 - Bkhargava_-_Grokaem_algoritmy

Терминология 159

Вы в любом случае оказываетесь в узле А, но цикл добавляет лишний вес.
Вы даже можете обойти цикл дважды, если вдруг захотите.

ОБ\4МК
6ЕС.:
2.1

Но каждый раз, когда вы проходите по циклу, вы только увеличиваете сум­
марный вес на 8. Следовательно, путь с обходом цикла никогда не будет
кратчайшим.
Наконец, вы еще не забыли наше обсуждение направленных и ненаправ­
ленных графов из главы 6?

~
е---8

~АПРА&ЛЕННЬli\ ~Е.НАПРА&ЛЕННЬli\
ТНФ ТРАФ

Само понятие ненаправленного графа означает, что каждый из двух узлов
фактически ведет к другому узлу. А это цикл!

В ненаправленном графе каждое новое ребро добавляет еще один цикл. Ал­
горитм Дейкстры работает только с направленными ациклическими графами,
которые нередко обозначаются сокращением DAG (Directed Acyclic Graph).

www.trk.kg