Графы и поиск путей

Главное

Количество путей в город = сумма путей в города, из которых в него ведут дороги. Кратчайший путь ищем перебором или по таблице.

Правила

1. Пути суммируются
2. Двигайся от начала к концу
3. Весовая матрица — длины дорог

Разберём пример

Из A в B 2 пути, из A в C 1 путь, из B и C в D по дороге. Путей в D?

3

Частые ошибки

• Считать пути дважды.

Потренироваться

Задания с проверкой и подсказками, схема темы и разбор ошибок с ИИ-репетитором — в уроке на платформе.