Карта связей: от стрелки до маршрутаЛогика / Различать стоимость и число рёбер Пробное занятие
Логика · шаг 36 из 64

Короткий путь: по шагам или по цене?

Различать стоимость и число рёбер · Сравнивать разрешённые маршруты

Около 19 минут 5 задач Подсказки рядом

В этом занятии

  • Различать стоимость и число рёбер
  • Сравнивать разрешённые маршруты
  • Обосновывать невозможность улучшения

Пригодится: Рекомендуем сначала пройти «Порядок без единственной очереди».

Ваш путь начинается с личного кабинета

Взрослый создаёт аккаунт для себя и отдельные кабинеты для школьников. У каждого — свой прогресс. Общие 48 часов знакомства начинаются с регистрации взрослого; школьники получают оставшееся время.

Войти или начать бесплатно
Учебное время начнёт считаться после нажатия
Понять — интереснее, чем запомнить.
Разберёмся перед практикой+

Короткий путь: по шагам или по цене?

Путь — последовательность разрешённых переходов. Для направленного графа каждый переход должен идти по стрелке. Если рёбра имеют стоимости, цена пути равна их сумме. Самый короткий по числу переходов путь может оказаться самым дорогим по времени или ресурсу.

Чтобы заявить минимум, недостаточно показать дешёвый маршрут: нужно исключить более дешёвые. В небольшой сети можно перечислить все простые пути. При положительных стоимостях повторение вершины создаёт цикл, который можно удалить и уменьшить цену, поэтому оптимальный путь не нуждается в циклах.

Достижимость означает наличие хотя бы одного пути. Она не обещает прямого ребра и не гарантирует обратного пути. Перед вычислением полезно отметить направление, единицу стоимости и ограничения: закрытые переходы или бюджет меняют множество кандидатов, а не только их рейтинг.

В маршрутной задаче отделяйте ответ от сертификата: число стоимости и сам путь проверяют разное. Если два маршрута имеют одинаковую минимальную цену, минимум единственный как число, но маршрут может быть неединственным. Это надо честно отразить в формулировке.

НА ПРИМЕРЕ

Разрешены А → Г за 9, А → Б за 2, Б → Г за 3. Какой путь самый дешёвый и какой требует меньше переходов?

  1. Прямой путь имеет один переход и цену 9.
  2. Путь АБГ имеет два перехода и цену 2 + 3 = 5.
  3. Критерии расходятся: меньше переходов не означает меньшую цену.

Попробуйте самостоятельно

Запишите рассуждения в черновик или сделайте построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.

  1. Нарисуй сеть с двумя разными оптимальными маршрутами и докажи минимальность цены.
  2. Придумай запрет на одно ребро и объясни, какие прежние решения исчезнут.

Читайте и разбирайте пример в своём темпе. К практике можно перейти, когда будете готовы.