Грокаем а Иллюстрированное пособие для программистов и любопытствующих

ЬЗВЕШЕННЫЙ ГРАФ


НЕВЗВЕШЕННЫЙ ГРАФ


раф с весами называется взвешенным графом. Граф без весов называется невзвешенным графом.
Для вычисления кратчайшего пути в невзвешенном графе используется поиск в ширину. Кратчайшие пути во взвешенном графе вычисляются по алгоритму Дейкстры. В графах также могут присутствовать циклы:
Ц
ИКЛ1 ПУТЬ,
НАЧИНАЮЩИЙСЯ С УЗЛА®,
ААОЖЕТ ВЕРНУТЬ­СЯ К УЗЛУ®
Э
то означает, что вы можете начать с некоторого узла, перемещаться по графу, а потом снова оказаться в том же узле. Предположим, вы ищете кратчайший путь в графе, содержащем цикл.
Е
сть ли смысл в перемещении по циклу? Что ж, вы можете использовать путь без прохождения цикла:
А
ОБЩИЙ
ВЕС:


можете пройти по циклу:
В
ы в любом случае оказываетесь в узле А, но цикл добавляет лишний вес. Вы даже можете обойти цикл дважды, если вдруг захотите.
Но каждый раз, когда вы проходите по циклу, вы только увеличиваете сум­марный вес на 8. Следовательно, путь с обходом цикла никогда не будет кратчайшим.
Н
НАПРАВЛЕННЫЙ
ГРАФ


НЕНАПРАВЛЕННЫЙ
ГРАФ


аконец, вы еще не забыли наше обсуждение направленных и ненаправ­ленных графов из главы 6?
С