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

ИНФОРМАТИКА: НАВЫКИ ДЛЯ ЕГЭ

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

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

Пример 1

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

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

Пример 2

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

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

Пример 3

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

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

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

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

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

Другие темы

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