Ступенькималенькие шаги каждый день

ИНФОРМАТИКА С ОСНОВ

Графы и кратчайшие пути

Три примера с разбором по шагам: от простого к сложному. Решите сами и проверьте ответ, регистрация не нужна.

Пример 1

Дороги двусторонние: AB=4, AC=4, BC=5, BD=8, CD=9. Других дорог нет. Найди длину кратчайшего пути A→D.

Показать разбор
  1. Выписываем все маршруты из A в D, в которых ни один пункт не повторяется.
  2. Складываем длины дорог на каждом маршруте: ABD = 12, ACD = 13, ABCD = 18, ACBD = 17.
  3. Самый короткий маршрут — ABD, его длина 12.
  4. Ответ: 12.

Пример 2

Дороги двусторонние: AB=3, AC=6, BC=2, BD=9, CD=8. Других дорог нет. Найди длину кратчайшего пути A→D.

Показать разбор
  1. Выписываем все маршруты из A в D, в которых ни один пункт не повторяется.
  2. Складываем длины дорог на каждом маршруте: ABD = 12, ACD = 14, ABCD = 13, ACBD = 17.
  3. Самый короткий маршрут — ABD, его длина 12.
  4. Ответ: 12.

Пример 3

Дороги двусторонние: AB=6, AC=4, BC=6, BD=10, CD=10. Других дорог нет. Найди длину кратчайшего пути A→D.

Показать разбор
  1. Выписываем все маршруты из A в D, в которых ни один пункт не повторяется.
  2. Складываем длины дорог на каждом маршруте: ABD = 16, ACD = 14, ABCD = 22, ACBD = 20.
  3. Самый короткий маршрут — ACD, его длина 14.
  4. Ответ: 14.

Закрепить тему можно за 20 минут в день

В кабинете ребёнок получает свой вариант заданий по выбранным темам и разбор после сдачи, а вы видите прогресс.

Попробовать 7 дней бесплатно

Другие темы

Нашли ошибку в задаче? Напишите нам.