Ищем лучший маршрут
Кратчайший путь минимизирует сумму весов, а не обязательно число рёбер.
В этом занятии
- Самостоятельно решить задачу по теме «Ищем лучший маршрут» и объяснить проверку результата.
- Составь граф, где путь с большим числом рёбер дешевле прямого, и объясни решение.
Пригодится: informatics9-graph-model
Разберёмся перед практикой+
Ищем лучший маршрут
Кратчайший путь минимизирует сумму весов, а не обязательно число рёбер. Если веса обозначают время, путь с тремя короткими переходами может быть быстрее прямого. В небольшом графе можно перечислить допустимые простые маршруты и сравнить их суммы.
Соблюдай направления и ограничения: нельзя использовать отсутствующее ребро. В наших задачах веса неотрицательны и маршрут описан полностью. Для больших графов нужны специальные алгоритмы, но сначала важно правильно построить модель и проверить найденный путь.
A→C весит 9, A→B — 3, B→C — 4. Через B получается 7, поэтому прямой путь не лучший.
- Перечисли допустимые маршруты.
- Сложи веса и выбери минимум.
Попробуй самостоятельно
Запиши рассуждения в черновик или сделай построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Составь граф, где путь с большим числом рёбер дешевле прямого, и объясни решение.
- Сначала предположи результат, затем проверь и объясни, что изменилось.
Источники и дальнейшее чтение
Материал изложен своими словами. Здесь можно проверить научные основания и подробнее изучить тему; часть источников — на английском.
Читай и разбирай пример в своём темпе. К практике можно перейти, когда будешь готов.