Граф маршрутов и кратчайший путь
Граф описывает объекты вершинами, а связи — рёбрами.
В этом занятии
- Самостоятельно решить задачу по теме «Граф маршрутов и кратчайший путь» и объяснить проверку результата.
- Нарисуй четыре станции и предложи две системы весов — время и стоимость. Покажи, как меняется лучший маршрут при смене цели.
Пригодится: informatics11-simulation
Разберёмся перед практикой+
Граф маршрутов и кратчайший путь
Граф описывает объекты вершинами, а связи — рёбрами. Направление и вес должны иметь явный смысл: возможность движения, время или стоимость. Кратчайший по числу рёбер путь не обязательно самый дешёвый по сумме весов.
Для поиска лучшего пути сравнивают допустимые маршруты и складывают веса. В учебных задачах все веса неотрицательны. Матрица или список связей задаёт ту же модель другим способом; отсутствие связи нельзя путать с ребром нулевого веса.
Есть дороги A–B:2, B–C:3 и A–C:7, граф неориентированный. Прямой путь весит 7, через B — 5. По суммарному весу выгоднее два ребра, а не одно.
- Уточни направление и смысл веса.
- Перечисли допустимые пути и сравни суммы, не только количество рёбер.
Открываем цифровую мастерскую…
Попробуйте самостоятельно
Запишите рассуждения в черновик или сделайте построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Нарисуй четыре станции и предложи две системы весов — время и стоимость. Покажи, как меняется лучший маршрут при смене цели.
- Сначала предположите результат, затем проверьте и объясните, что изменилось.
Источники и дальнейшее чтение
Материал изложен своими словами. Здесь можно проверить научные основания и подробнее изучить тему; часть источников — на английском.
Читайте и разбирайте пример в своём темпе. К практике можно перейти, когда будете готовы.