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

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

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

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

Пример 1

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

Показать разбор
  1. ABD: 12.
  2. Длины всех простых путей: ABD=12, ACD=13, ABCD=18, ACBD=17.
  3. Кратчайший путь имеет минимальную длину.
  4. Ответ: 12.

Пример 2

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

Показать разбор
  1. ABD: 12.
  2. Длины всех простых путей: ABD=12, ACD=14, ABCD=13, ACBD=17.
  3. Кратчайший путь имеет минимальную длину.
  4. Ответ: 12.

Пример 3

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

Показать разбор
  1. ACD: 14.
  2. Длины всех простых путей: ABD=16, ACD=14, ABCD=22, ACBD=20.
  3. Кратчайший путь имеет минимальную длину.
  4. Ответ: 14.

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

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

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

Другие темы

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