Главная идея

Сначала нарисуй граф по таблице, потом решай

В таблице дорог число на пересечении строки и столбца — длина дороги между двумя городами, пустая клетка — дороги нет. Длина пути — сумма весов. Количество путей — это перебор, и веса в нём не складывают. Условие «через пункт» делит путь на два куска, а «не через пункт» вычёркивает пункт из графа.

длина = w₁ + w₂ + … d(X) = min(d(Y) + w) через X: d(А→X) + d(X→Ф)
01

Читаем таблицу

Строка — один город, столбец — другой. Число в клетке — дорога между ними, пустая клетка — дороги нет. Таблица зеркальна: граф неориентированный. Рёбра читай выше диагонали, чтобы не записать дорогу дважды.

02

Длина или количество

Длина пути А→Б→Г — сумма весов. Количество путей — сколько разных последовательностей вершин ведут из А в Г; веса не используют. Вершины в пути не повторяются.

03

Кратчайший путь

Выпиши пути и сложи веса или подпиши вершины расстояниями: d(А) = 0, а для остальных d(X) = минимум из d(Y) + w по подписанным соседям. Подписывай в порядке возрастания расстояния.

04

Через и не через

Через X: кратчайший путь А→X плюс кратчайший X→Ф. Не через X: вычеркни X и его дороги и решай обычную задачу. Количество путей с запретом считай так же.

Не путай: если спрашивают «сколько путей», сумма весов не нужна и ответом быть не может. Если спрашивают «длину кратчайшего пути», нужна сумма весов.
Управляемая модель

Подпиши вершины кратчайшими расстояниями

неориентированный граф с весами
Подписывай по порядку возрастания расстояния: d(X) — минимум из d(Y) + вес дороги Y—X по уже подписанным соседям.
Решаем вместе

Четыре разобранные задачи

Изучено: 0/4

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

Проверка перебором

Все пути, длины и количество

  1. 1

    Нарисуй граф по таблице

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

  2. 2

    Определи вопрос

    Длина — суммируй веса. Количество — перебирай пути, веса не нужны. Есть условие «через» или «не через»?

  3. 3

    Примени условие

    Не через X — вычеркни X. Через X — найди два куска и сложи.

  4. 4

    Проверь перебором

    Выпиши все пути и сравни ответ. Не забудь прямой путь и пути через две вершины.

Задача и все её пути

Твоё решение

Самостоятельная работа

Шестнадцать задач с проверкой и разбором

Верно: 0/16

Ответ — одно число (или «да» / «нет»). Рисунок графа по таблице можно открыть кнопкой, но сначала попробуй прочитать таблицу сам. После первой проверки открывается полный разбор задачи.